A quick note before we get started. I will use a term machine and automaton interchangeably they do mean the same thing and the plural of automaton is automata A finite state machine also known as a finite automaton is a simplest computational model we can construct It has extremely limited memory, but it can still do many things and these machines are actually very often used in our everyday devices For example The controller for switching an oven on or off is a finite state machine This controller will have two states, ON and OFF Let's say this oven is brand-new. So it first starts in the OFF state Whichever state we start in is called the start state and we have a little arrow pointing at it Now when the button controlling the controller is pressed it goes into the ON state and if the button is pressed again It goes back into the OFF state Pretty simple, right?
So let's build on that understanding and construct a slightly more exciting machine Let's construct a machine that takes in a string of weather data as input and tells us whether a heatwave occurred in a given year In India, the India Meteorological Department considers it a heatwave if the maximum temperatures reach 45 degrees Celsius for two consecutive days So using this definition of a heatwave, let's construct our machine Let's say this is our start state and we're just going to call it q0 If we hit a day where the temperature is over 45 degrees we transition into this new state which we will call q1 And if we hit another day where the temperature is over 45 degrees we transition into this other state which we will call q2 Since the heatwave is defined as having two consecutive days with temperatures over 45 degrees then when we reach q2, we know that a heat wave had indeed occurred So we call q2 an accept state and to represent the accept state we draw another circle around q2 And now to complete our machine, going back to our start state q0, if the temperature is not over 45 degrees We will remain in the same state and if we are in state q1 and the next temperature read drops below 45 degrees Then we will go back to our start state q0 Because for it to be considered a heat wave temperatures must be over 45 degrees for two days in a row and if we are already in our accept state q2, we don't have to go anywhere because the heat wave has already occurred And finally, we'll just modify our machine a little bit more and let's use a 1 to represent a day with a temperature over 45 degrees and we use 0 to represent a day with a temperature less than 45 degrees And there we have it, our finite automaton in which we will now call M, will tell us if a heat wave had occurred Notice that the automaton will enter the accept state if it takes in any string containing two consecutive 1s as input All these strings that eventually arrive at one of the machines accept states are a part of the language of the machine So the language of this machine is a set of all strings containing two consecutive ones We say that the automaton recognizes this language and it accepts all the strings in the language and rejects those that are not in the language So M accepts 11, 110, 0110, and so on This kind of automaton is called a deterministic finite automaton or DFA for short They are called deterministic because for every symbol of an input string read we will always know what the next state will be The next state is determined What we have here is a state diagram of the DFA And to formally define DFAs we use a five-tuple Q is a finite set of the machine states and for our machine M that would be the set containing q0, q1, and q2 Sigma is a finite set called the alphabet, which are the kinds of symbols that are recognized by the machine So in this case, it is a set containing 1 and 0 Delta is the transition function which tells us where states transition to given an input symbol For example q0 transitions to state q1 when it reads a 1 and remains in q0 when it reads a 0 q1 transitions to q2 on a 1 and back to q0** on a 0 And when we reach q2 we will always remain in q2 q0 is a start state And finally F is a set of accept states also known as final states sometimes Which in this case would just be the set containing q2 One final note on finite automata A language is also a regular language if it is recognized by some finite automaton So the language containing all the strings of two consecutive 1s is a regular language since we had constructed an automaton that recognizes it Now that was quite a bit of information. So let's just summarize what was said in this video 1. DFAs are give-tuples that can be represented with state diagrams 2.
If the last symbol of an input string causes the machine to be in an accept state Then the Machine accepts the string 3.
