A quick note before we get started, I will use the 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 the 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. construct a machine that takes in a string of weather data as input and tells us whether a heat wave occurred in a given year.
In India, the India Meteorological Department considers it a heat wave if the maximum temperatures reach 45 degrees Celsius for two consecutive days. So using this definition of a heat wave, 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 the start state, 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 a heat wave 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 red 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 a 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 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 ones as input. All these strings that eventually arrive at one of the machine's accept states are a part of the language of the machine. So the language of this machine is the set of all strings containing two consecutive ones.
We say that the automaton recognizes this language and it accepts all the 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 5-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 the 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 q1 on a 0, and when we reach q2, we will always remain in q2. q0 is the start state. And finally, f is the 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 with two consecutive ones 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 5 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. If the last symbol of an input string causes the machine to be in an ACCEPT state, then the machine ACCEPTS the string. The language of a machine is the set of all strings it accepts, and finally, a language recognized by some finite automaton is called a regular language.
I will now leave you with all this to digest, and a very gentle reminder that as you may start constructing DFAs, designing automata is a creative process that takes time and practice, the same way it does to design any other work of art.