A-Level Comp Sci: Finite State Machine

how's it going guys it's Chris here and this video covers the AAS topic of finite state machines traffic lights are an example of an SSM by the end of the video you should be able to understand why here's the agenda we'll start with defining the term finite state machine and looking at their key characteristics then we'll move on to look at two ways finite state machines can be represented so a finite state machine is a computing machine that has a fixed set of possible states a set of inputs and a set of possible outputs the phrase fixed set of possible states is just another way to say finite States and finite is a key word because whenever we implement a finite state machine in hardware or software we only have limited memory space to play with that's why it's finite finite state machines don't actually need to have an output you'll only see ones that do at a level you might also see the term finite state automation to describe a finite state machine that has no output finite state automata is the plural version now despite you using a picture of an old-fashioned mechanical machine when referring to a finite state machine we often don't mean a literal physical system but instead an abstract creation we use to model simple computation and decision making in this video we'll look at one physical example and one that's completely abstract just so you're familiar with both just in case you haven't quite understood what a finite state machine is yet let me just reimburse eyes really their conceptual machines which could take some input maybe a letter or a number or a physical input like a user pressing a button whatever the input is either causes a machine to just remain in its current state or to change the state if then for example you moving a slider on one finite state machine could just keep the machine on like it was already whereas applying the same input to a different machine might actually turn it off in this example the state of the machine is being either on or off now we need to mention a key feature of a finite state machine which is that the state it changes to is based on both the current state and the input value to demonstrate this think about a ballpoint pen which is a simple example of a finite state machine when you apply the input ie you pressing the button the machine changes state so that the pen nib extends however when you press the pens button again the nib retracts this demonstrates that despite the input being the same the result is different because the current state is taken into account as well long story short applying the same input multiple times doesn't necessarily lead to the same result this property means the machines entire history can be summarized in its current state how it actually got that state is irrelevant you can just look at the current state and its input now we have some theory nailed down let's look at the first way we can represent FSMs which is with state transition diagrams these show the machines behavior visually and here's the state transition diagram for the ballpoint pen example we just talked about a circle represent the state of the machine as you can see we have two states in this example which are the pen either being retracted or extended we've labeled the state s0 and s1 but we could add a key to connect meaning to them arrows represent a transition to a state and we label them with the input that has triggered the transition just like we looked at when the pen current state is retracted at s0 and you press the button the pen transitions to a state with an ibid extended at s1 before we move on to the next example here are two other symbols you need to know the initial state is where the machine starts from and resets to naturally you can only have one initial state a double circle represents an accepting state you might also hear called the goal states and it's the state which shows whether an input is acceptable you can have more than one accepting state it is a more complicated state transition diagram but it's not as bad as it looks if actually to do with another area of your course regular expressions but don't worry if you haven't covered that yet you don't really need to have done so in order to understand this all regular expressions can be represented as state transition diagrams we're going to use a B asterisks as our example regular expression here the asterisks means 0 or more so this regular expression means you want 1a inputted then followed by as many bees as you want despite it being a bit abstract the point of this FSM is to determine whether the input given is acceptable according to this regular expression our possible inputs are only going to be the letters A and B right let's break down this diagram then as you can see the state labeled zero is the initial state so we can start there if our first input is a then you transition to one which is the accepting state if you then inputted B then you just remained at one because the arrow on the diagram loops back on itself no matter how many B's you add from one you just keep transitioning back to that accepting state hopefully you can see that this matches our regular expression and it being at the accepting state is telling us that our input string is okay however if you then input an A from one or you started off from zero with a B then you have a problem because the Machine transitions to two instead no arrows go from two to one so you're stuck here forever our words essentially an unaccepting state you just keep inputting A's or B's from two without a change of state it means our string doesn't match the regular expression now although this example may seem even more boring than the pen one using these diagrams regular expressions is actually a really important tool computer scientists let's now look at our second and final way of representing finite state machines which is with state transition tables like the truth tables you find in logic and show the effect different inputs have on the current state here's the one for the pen example you can see our three columns which are input current states and next state at a level we also might add an output column if it were applicable by current state we mean the state of the machines in before you add the input and the next state is the one machine transitions to because of the input just so you can see both representations together and see a slightly more complicated state transition table here's the regular expression state transition diagram from earlier as you can see for each possible current state we test each possible input and show the effects of this in the final column when constructing these cables you just need to make sure you are methodical and cover every possible combination I suggest you now pause the video and see if a cable make sense to you according to the diagram and vice versa and we're done let's have a quick recap we have to find the term finite state machine this could be a really standard two more question so learn this definition a finite state machine is a computing machine that has a fixed set of possible States a set of inputs that change the state and a set of possible outputs hopefully now also understand that the next state is based on both the current state of the machine and the input this should be extra apparent when you look at the two different representations state transition diagrams and safe transition tables thanks for watching

Channel: justAlevel

Views: 45,264

Rating: 4.9661655 out of 5

Keywords:

Id: 4rNYAvsSkwk

Length: 8min 21sec (501 seconds)

Published: Mon May 22 2017