hello everyone welcome to the next lecture in theory of computation and in this lecture we will be studying about finite state machines all right so let's get started so finite state machines it is also known as finite automata and this finite automata is divided into two broad categories the first one being finite automata with output and the second one being finite automata without output and finite automata with output we again have two categories namely Modi machine and mealy machine and in finite automata without output we have three categories namely deterministic finite automata or DFA non-deterministic finite automata or NFA and Epsilon non-deterministic finite automata or epsilon NFA all right so in this lecture we will be mainly focusing and studying about our deterministic finite automata or DFA okay so DFA it stands for deterministic finite automata before we start off with DFA let us remember two important properties of finite state machines that we should always remember and they are finite state machines it is the simplest model of computation and also finite state machines has a very limited memory so these are two important points that we should always keep in mind before we study anything related to finite state machines okay now we can start off with deterministic fire automata or DFA now to make DFA clear let us take a simple diagram that will make the structure of DFA play to us so this diagram here it shows us the structure of for deterministic finite automata or D F a so first when you look at this diagram you may feel confused what are these what do we see here we see some circles labeled as ABCD we see some edges some arrows pointing here and there and we have seen some labelings like 1 1 0 0 1 1 and what are all this okay so I will explain to you what this means so that the structure of this DFA becomes clear to us so first of all the first thing that we need to know our states these circles represented by a B C and D these circles are known as States okay ABCD are States and then we see some edges C one edge goes from A to B another as u goes from B to a and here also we see an edge going from A to C and another from C to a and here we see one going from C to D and from D to C B to D D to B so what are these these edges are actually the transitions so what does this mean this transition means that suppose we are in state a and this edge labeled with one this labeling of edges are known as inputs these are our inputs so it what it means is that when I am in state a and if I get input 1 if the input I get is 1 so my state a goes from A to B all right and in the same way if I am in state a and if I get input 0 then what happens state a goes from A to C ok and let's take one more example suppose I am in state C and I get input 1 so where do I go I go from C to D and in D if I get input say 0 it goes from D to B so that is how the transition occurs so this labelings of the edges they are our inputs and circles are our states so it shows how the state's transits from one say to another on getting certain inputs ok so though that was about the states and the inputs now we see that there is something different about state a and state D so what are they it stay a we see an arrow that is coming from nowhere and pointing to a so what is this this means that a is the starting state or the initial state of this DFA whenever you see an arrow coming from nowhere pointing to a state that shows that that is the initial state or the starting state and if you look at state D there is something different what is that every other states have one circle but this state D has two circles it has a double circle around it and what does that mean whenever you see a double circle it means that that is the final state order terminating state so this state D represented by two circles it is the final state of this D F a alright so those were the main things that you need to know about a DFA so that makes the structure of the effect clear to us okay so now let us write down the formal definition of this DFA so every DFA can be defined using five tuples which are Q Sigma Q naught F and L every DFA can be defined using these five tuples now let us see what are disturbance what do they mean first of all we have Q Q is the set of all states the set of all states is known as Q and what is Sigma Sigma is the inputs our inputs is represented by Sigma and then the next one is Q naught what is Q naught Q naught is the start state the start state or it's also known as the initial state it is an initial state okay and then the next F F is a set of final States the set of final state is known as F so here in this example we had only one final state but we could even have more than one final States so that is why I have written set of final States alright and the last one is Dell so what is Dell Dell is a transition function it is a transition function that map's okay from Q cross Sigma to Q it is a transition function that map's Q cross Sigma to Q you're worried even if I don't understand this this will become clear when I take the example I will be showing you in the exam ok so now let us try to write down what are the values for these five tuples for this example that we have taken you and for our particular DFA what are the values for this tuples first of all we have Q so what is Q here Q is a set of what are the set of all states a B C and D a B C and D this is our Q and what is our Sigma Sigma is the inputs where are our inputs we have inputs here 0 and 1 zeros and ones are the inputs we use here so it is 0 and 1 okay so that is a Sigma and what is the next one Q naught Q naught is the start state or the initial State so I already told you whenever we see an arrow coming from nowhere pointing to a state that is the start state so our start state here is a a ok and then the next one is F F is the set of final States so what is the final state here D we have only one final state whenever you see a double circle that represents our final state so I should probably put it in a bracket because it could be more than one but in this example it is only one so set our set of final States is D and then the last one del del is a transition function from Q cross Sigma to Q now to demonstrate this let me take a table over here I'll use this table to explain what is there so for that let me have this table where this top part will be my input 0 1 and I'll have my state's in this part a b c and d alright now let's see what is this what does this mean so suppose I am in state a and I get input 0 so what happens when I am in state a and I get input 0 it goes to state C right a to see I'm in state a if I get input 0 I come to state C alright and if I'm in state a and if I get input 1 what does it happen what happens it goes to state B see over here when we there is input 1 it goes to state B B now let us come to state number B in B when i get input 0 where does it go it goes to state d and when I get input one where does it go from be if I get input one it goes to a all right now I'm in state C suppose I'm in state C and if I get input zero where does it go it goes to state a say it a and if I am in state C and get input 1 5 misstate C and get input 1 it goes to state D all right and if I'm in state D and I get input 0 where does it go it goes to state B and in from state D if I get input 1 it goes to state C so this is the transition function there it maps from Q cross Sigma 2 cube so that is how we write the transition function for the DFA so this was the basic structure of a DFA I hope you understand ER storage so these are the main things that you should remember and this is the structure of the DFA and we will take some examples in the following lectures which will make it more clear to us so thank you for watching see you in the next lecture [Music] you [Music]