How to construct a DFA in Automata | Shortcut Easiest Way Step by Step | Part-01



hello friends welcome back in this video we are going to discuss another very important topic in theory of computation which is construction of a DFA this is a topic from which you will definitely get at least one question and this is really a very important topic from the examination point of view so let us start with the construction of a DFA there are various types of problems that are being framed and asked from this topic in this video we will discuss one of such types so now let us see what is the type one problems that are asked from this topic so this is of a type one problem for Strings ending with a particular substring in this type of problems you will be given a language consisting of the strings ending with a particular substring you will be given a particular substring and you will be asked to draw the DFA for a language containing all the strings ending with that particular substring there is not much theory to be studied under this topic so let us directly come to the steps that are involved in the construction of DFA for such type of problems step one says decide the minimum number of states required in the DFA and draw them so in the first step we will calculate the minimum number of states that will be drawn in the DFA and then we will draw those states for calculating the minimum number of states we will make use of this rule this rule says that all strings ending with n lengths substring will always require minimum n plus 1 States in its DFA right so if the length of the substring is N we will be requiring n plus 1 states in the DFA for example consider we have this regular expression we are given a language over input alphabets a and B and we are given this regular expression right this regular expression says that the that the strength of those language all this ends on a particular substring Z right what comes before Z does not matter but all the strings must end on the substring Z so if the strings of above language will always end on Z so if the length of Z is equal to n then the DFA will require a minimum n plus 1 straights right I hope this step is clear to you I and it will be more clear to you when we will start solving the problems now let us move to our step two so this is a step two step two says decide the strings for which you will construct the DFA so in step two we have to decide the strings for which we will construct the DFA right how to decide the strings I will be discussing when we will start solving the problems but for now you should remember that in step two we have to decide the strings for which we will construct the DFA right now let us come to our step three step three says construct the DFA for the above decided strings so in step three we will start constructing the DFA for the strengths that we have decided in step two while constructing the DFA you have to remember this Golden Rule which if you ignore you will definitely finished up constructing the wrong DFA right so this rule says always prefer to go with the existing part always all this and always prefer to go with the existing part create a new part only when you can't find a path to go with right so we have to always make the use of the currently existing part and we we will construct a new path only and only when we can't find such a part right we will see in the problems when we will start solving now let us come to our step for step forces after drawing the DFA for the above decided strings send the left possible combinations to this starting state and not over the dead configuration so in step 4 when we have finished constructing our DFA we will send the left possible combinations to this starting state and not over the dead configuration so these are our steps and these steps will be more clear to you when you start solving the problems so now let us start solving our problems so this is our problem were one we have been said draw the DFA for the language accepting strengths ending with 0 1 over input alphabet 0 & 1 in this question we have to construct a DFA for the language accepting all these strengths over input alphabet 0 & 1 that ends with 0 1 I hope you got this question so now let us start solving this question first of all let us write the regular expression for this language it's not compulsory but it is a good practice if we write the regular expression for the given language so the regular expression for this language will be 0 plus 1 star 0 1 right this is the regular expression representing all these strings / 0 & 1 ending with 0 1 this is the ending substring 0 1 and before this substring we can have anything or nothing we can have 0 or any number of zeros 1 or any number of ones or any possible combination of zeros and ones so this is our regular expression now let us apply our step 1 our step 1 was to calculate the minimum number of states that will be drawn in the DFA and then we have to draw those states so in this regular expression the substring is 0 1 the length of the substring is 1 plus 1 which is true so the length of the substring is 2 so the minimum number of states that will be required in the DFA will be 2 plus 1 that is 3 so now we will draw 3 states like this the first state will be Q naught this will be our starting state or initial state then this set for the second state Q 1 and then the third state which is which will be of a final state let us say Q 2 and because this is our final state so we will double circle it like this now let us apply our step to our step two was to decide the strings that we will consider for constructing the DFA now I will tell you how to how you have to form those strings the first string we'll be this substrate itself so we will write here 0 1 right so you have to remember the first string that we will have to consider for constructing the DFA will be the substring itself which is here 0 1 so I have written the first string as 0 1 now let us know how to write the other strings for writing the other strings that we will be considering for constructing the DFA you will be beginning from the very starting of this string and will be writing these strings of all the possible lens like the possible lengths will be 1 & 2 for this case so we will write here 0 which is length 1 string and then 0 1 like this had there been any other element say 2 then we will write B then we will be forming another strings 0 1 & 2 right I hope you got this point now what we will do will simply place this string in front of all the strings that we have derived using this string so we will write here 0 1 and then again 0 1 right so these are the strings that we will be considering for constructing the DFA if we construct the DFA for these strings and plus we apply our step four then we will get the DFA for the language accepting strings over input alphabet 0 & 1 ending with 0 1 right I hope you got the point so now let us construct the DFA considering these strings the first string is 0 1 using this string we have to read from above initial state to the final state since we have two input alphabets so how we will write it for 0 we can make a transition from Q naught to Q and then for the alphabet 1 we can make a transition from q1 to q2 right I hope you call this point now it is evident from this much DFA that you can't write any more transition for 0 for this state Q naught because MDF a for each state for each input alphabet there there is only one transition right I hope you know this point so now we can't write any transition of Q naught for 0 and for Q 1 for 1 right I hope you got the point now for this string we will construct the DFA and always remember that we have to use the currently existing part always and we will create a new path only and only when there is no such path existing right so now for this string we have to reach from the initial state to the final state so 0 0 & 1 so initial state we are initially at the initial state and then for 0 we can make a transition to Q 1 and then we have to use 0 and then we have to make a transition for 0 so what we can do is we can make a transition of Q 1 like this right because you can't write a transition for this 0 because if you wanted to write 0 here that would not be possible because you have already returned a transition for 0 for state Q naught so you can only write Q for the transition for 0 on this state you can't write here also because then for this string you can't reach from the initial state to the final state so you will have to write the transition for 0 only at this state I hope you got this point so now for 0 0 & 1 we can from the initial state to the final state so we covered this string as well now let us consider our third string and we will reach from the initial state to the final state we have 0 1 0 1 so 0 1 we are using the existing path you can see 0 1 and then we have to again make a transition for 0 so what we can do is we have we will have to make a transition of 0 on this state we can't make a self loop like that because that won't give rise to our reaching from initial state to the final state so what we can do is we can make a transition like this right 0 and then 1 so for 0 1 0 1 you have a transition like this 0 1 0 & 1 so you can see that always we are using the existing path so now after we have covered all these strings that we have formed so our step 2 gets completed our step 3 gets completed now we will apply our step 4 our step 4 was after drawing the DFA for the above decided strings send the left possible combinations to the starting state right so we know that in the DFA for each input alphabet you will be having the transition for all these states right so for if we consider the initial state this Q is 0 or qunit we have a transition for 0 but we don't have a transition for 1 and we have to send the left possible transitions to the starting state so what we can do we can make a transition like this so now Q naught has a transitions for 0 as well as for 1 I hope you got this point now let us see our state Q 1 for Q 1 we have the transition for 1 and as well as for 0 so there is no need to do anything right now let us see for q2 for q2 we have a transition of zero but we don't have a transition for one so what we will do we will make a transition of Q 2 to Q naught Q 0 for the input alphabet 1 like this so all the steps get completed so this is our required DFA I hope you got this problem you will get much more clarity when you will solve more and more problems so now let us move to our problem number 2 so this is our problem number 2 we have been said draw the DFA for the language accepting strengths ending with a BB over input alphabet a and B so in this question we have to draw a DFA for the language accepting the strings over input alphabet A and B ending with a BB right so let us start solving the problem first let us write the regular expression for the given language the regular expression will be a plus B star and then a b b right this is the regular expression for the given language this is the substring on which the strings must end right and before this substring we can have anything or nothing right as we did in the last problem so now let us move to our step 1 of a step 1 boss to calculate the minimum number of states in the DFA and then draw those states because the length of the substring here is 3 as you can see there are 3 alphabets so 3 plus 1 will be 4 so there will be 4 minimum States in above D if a so now let us draw these states the first state will be Q 0 this will be our initial state then state Q 1 which will be our second state and then state Q 2 this is our third state and then state Q 4 sorry Q 3 this is the fourth state and this will be our final state as well so we will double circle it like this right I hope you got up till here now in our step two we have to decide the strings for which we will be constructing the DFA as I told you the first string will be the substring itself so we because the substring here is ABB so we will write here a B B right now for forming the other strings we will start from the very beginning from here and we will write the strength of length one two and then three in this manner a a B and then a BB right I hope you got this point now we will copy this string in all these strings so a b b a b b and then a B be right now in we'll start our step three in step three we have to start constructing our DFA for these decided strings so our first string is ABB so we have three alphabets and we have three parts so for each alphabet we will move from one state to the other state like this for a and this is for B and this is for the other B right this is clear now our second string is double a double B always remember we will make the use of the currently existing path so initially we are at the initial state and we have to make a transition for the input alphabet a yes we have a transition for a so using this transition we will move to state Q 1 and then we are at the state Q 1 and when we are at Q 1 we have to make a transition for a but we don't have a transition for a right so we will be making another transition and the other transitions in further are BB so what if we already have BB so what we can do is we can make a transition of input alphabet a at this state Q 1 like this right so now our transition gets completed a a B B so using this string we are able to reach from the initial state to the final state right again I am telling you that for this at this state we can try the transition for a because we have already returned a transition for a and in the DFA for each state there is a unique transition for each input alphabet right so from this DFA it is evident that for the state given all the transitions are completed and we can't write any more transition for this state Q 1 so we will always ignore it and now we will check the other string the other string is a b a b b so let us start from the initial state initial state we are at Q 1 Q naught sorry and then using a yes the s we have a transition for input alphabet a so using this transition we will reach at Q 1 and then Q 1 we have to make a transition for B yes we have a transition for B so we will using this transition we will reach to state Q 2 and then Q 2 we have to make a transition for input alphabet a but as you can see that we do not have a transition for a and then we have to do a transition of B B so what we can do is we can make a transition for input alphabet a from state Q 2 to Q 1 like this right I hope you got this point so now we have for a b a b b a.b a.b b so for the string also we are able to reach from the initial state to the final state now let us consider our last string the last string is a BB a BB so all this make the use of the currently existing path so a B B yes we have the currently existing path and then again we have to make a transition of a BB so using a BB we are at the final state q 3 and then we have to make a transition of a BB so BB we are already having so what we can do is we can make a transition for input alphabet a from state q3 – q1 like this so this is a right I hope you got this point now we are done with step 2 and step 3 now let us apply our step 4 then left all the left possible combinations will be sent to the initial state so for the starting state of the initial state we have a transition for input alphabet a but we don't have any transition for input alphabet B so what we can do is we can we have to send the transition for input alphabet B to the starting state and this is the starting state itself so we will make a self-loop like this this is 4 this is a transition for input alphabet B now check for this state yes for this state we are done we have a transition for a as well as for B lauda check for Q 2 for Q 2 also we have a turn for a as well as for B and for q3 we have a transition for a but we don't have any transition for B so what we will do is we will send it to the initial state like this so our step four also gets completed and now above all the steps are done so this is our required DFA I hope you got this problem right so now let us move to our next problem problem number three so this is our problem number three we have been said draw the DFA for the language accepting strings ending with a BB a over input alphabets a and B in this question we have to draw a DFA for the language over input alphabets a and B where all the strengths and with a be BA right so as usual we will write the regular expression for the given language the regular expression for this language will be a plus B star and then a b b:a right this is the substring at which all the strings must end and before this substring we can have anything or nothing as always right now you can clearly see it at the length of the substring is four as there are four alphabets in this substring so the minimum number of states that we will be requiring among DFM will be 4 plus 1 that is 5 so we will write here 5 minimum number of states in the DFA equals to 5 now let us come to a step two in step two we have to decide the strings for which we will be constructing our DFA so let us start writing the strings the first string will be the substring itself so we will write here a b b:a right now we will write the other strings for writing the other strings we will start from the very beginning of this string and we will write the strengths of all the possible lengths 1 2 3 & 4 like this a b a b b and then a b b and a now we will copy the strength in all these strings like this a BB a a b b:a a b b a and then of a b b:a so now we have formed all the strings from which we will be constructing our DFA so now let's start number step 3 of a step 3 is the construction of DFA let us start the construction of DFA sorry I forgot to draw those states in the first step but now we can draw it now so we have to draw the five states we will draw the five states like this Q naught this will be our initial state then the second state Q 1 then the third state Q 2 then the fourth state Q 3 and now the fifth state Q 4 and because this is our final state so we will double circle it like this right I hope you got till here so now let us start constructing our DFA for the decided strings our first string is a BBA for alphabets and for parts so for each alphabet we will make a transition from the one state to the other state like this so a B B and then a right so now let us consider a second strict but always remember that we have to use the currently existing part so now double a double B a so initial we are at the initial state Q 0 our first input alphabet is a yes we have a transition for a so we will use it and we will move to state Q 1 and then Q 1 we have to make a transition for a we do not have a transition for a so we will make a transition for a we can't make it here or on the other states so we will have to make it at the Q 1 itself so we will write here a our transition for a and then a BBA so a B be a again a ABB a a a be B a so for the second string we are able to reach from the initial state to the start final state right now let us consider our third string our third string is a be a BB a so initially we are at the initial state Q naught so for Q naught we will make a tansy we have to make a transition for a yes we have a transition for a so we will use it and move to state Q 1 and then Q 1 we have to use B yes we have it and then we have to make a transition for a but we do not have it and then we have a for B ba yes we have this BB a so what we can do is we can make a transition from Q 2 to Q 1 for the input alphabet a like this right so for the third string now we are able to reach from the initial state to the final state a B a B D a so our third string is also completed now let us check our fourth string of a fourth string is a BB a BB a so a B be a yes we have a transition for a as well so a BB a is covered so now we will do for B be a we don't have a transition for be here so we will make and then be a yes we have a transition be a so what we can do is we can make a transition from Q 4 to Q 2 for input alphabet B right some people commit here a mistake what they do is like we have this string a BB a BB a so what they do is a BB yes a maybe they see it and then the C a and then B B a so they see that we have B ba so what they do is they make a transition from q3 to q1 for the input alphabet a but that would be wrong because I have always told you that you have to consider the existing path if there is a part it exists you have to always consider that first so because we have there hey so we considered it and then we went for B be a B be a right so I want you people to never commit mistake here at this point right so our last string is a BB a a BB a so let us check a B be a yes we have it and then we have a BB a but we don't have a transition for input alphabet a on this state so we will have to make it and then we have B ba so BB a we already have it so what we can do it so what we can do we can make a transition from Q for Q 2 to Q 1 for input alphabet a like this right so now we have it a be B a a B be a I hope you got this point right so now we are completed with our step 3 now we have to apply our step 4 in step 4 we have to send all the left possible combinations to the starting state so now let us check other states one by one first of all we will consider our initial state Q naught or Q 0 so for Q 0 we have a transition for input alphabet a but we do not have any transition for input alphabet B so what we will do it we have to send the transition for input alphabet B to the starting state because because this is a starting state itself so we will make a self-loop like this for the input alphabet B right now let us consider q1 for q1 we have a transition for input alphabet a as well as for input alphabet B so we need not to do anything so now let us consider q2 for q2 we have a transition for B but we do not have a transition for no yes we have a transition for a here so we need not to do anything now let us come to our Q 3 Q 3 for q3 we have a transition for a but we do not have a transition for the input alphabet B so what we can do is we have to send it to the initial State like this so this is our transition for input alphabet B right now let us consider a final state for final state we have a transition for B as well as for a so there is no need to do anything so fourth step also gets completed so now when all the steps are done we are done with the required DFA this is our required DFA I hope you caught this problem as well so now let us move to our last problem problem number four so this is our programmer for we have been set draw the DFA for language accepting strings ending with 0 0 1 1 / input alphabets 0 & 1 so in this problem we have to construct a DFA for the language over input alphabet 0 & 1 accepting all the strings ending with double 0 double 1 right I want you people to try this problem first and in case you don't get it then only refer my solution right so let us start solving this problem first let us write the regular expression for the given language the regular expression will be 0 plus 1 star and then 0 0 one one right this is the substring at which all the strings must get end so we have written like this and before this substrate we can have anything or nothing as always right so now let us apply our step one our step one is calculation of the minimum number of states so if the length of our substring is four as you can clearly see there are four input alphabets so the minimum number of states in the DFA will be 4 plus 1 that is 5 I hope now this has become very easy for you after doing so many problems so now let us move to our step to our step 2 else we have to decide the strings for which we will construct our DFA so as we know that the first string that we will be considering is the substring itself so we will write here double 0 and then double 1 right so now for forming the other strings we will start from the very beginning and start writing all these strings of all possible ends so we have 0 and then 0 0 and then 0 0 1 and then double 0 double 1 right now we will simply copy this string in all these strings so we have 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 right so we have formed all these strings for which we will be constructing our DFA so now let us apply our step 3 our step 3 is the construction of DFA so now let us construct our DFA sorry I forgot again to draw all these states but no problem we can draw them now right we have five states in our DFA so we have Q 0 of a first state which will be able find initial state also and then state Q 1 which will be our second state and then state Q 2 our third state and then state Q 3 of a fourth state and then state Q 4 which will be our fifth state and final state as well so we will double circle it so now let us draw above DFA we will consider first this string we have 0 0 1 1 4 input alphabets and four paths to cover so we will use each alphabet to move from one state to the other state like this 0 0 1 1 right we are done with the first string now let us move to our second string our second string is triple zero and double one remember always use the existing path so initially we are at the initial state so for 0 we have to make a transition we have a transition for 0 so we will move from state Q naught to Q 1 and then again we have to make a transition for input alphabet 0 so yes we have a transition for 0 so we will move stick from state Q 1 to Q 2 and then we have to make a transition for 0 we cannot write a transitions of 0 for these two states because we are already done with these two states right so we will make a transition like this I hope you got this now all right and then double 1 yes we have double one so triple 0 0 0 0 and then 1 1 so now we are done with the second string as well now come to above third string our third string is 4 times 0 and then 2 times 1 so 0 0 0 and 0 we can cover all the 4 zeros here 2 zeroes this and we can cover as many zeros as we want so we want to 0 so we can take two zeros from here so we have total four zeroes 1 2 3 and 4 so 0 0 0 0 and then 1 1 so we have already done with the third string there is nothing to do now right so now let us come to would string our food string is 0 0 1 0 0 1 1 so initially we add this state so we have to make a transition for 0 so 0 we will use and you will come to state Q 1 and then again we have to make a transition for the input alphabet 0 so we will move from state Q 1 to Q 2 0 and then we have to make a transition for one yes we have one so we will use it and we will move to state Q 3 and then we have to make a transition for 0 right and then we have 0 1 1 yes we have 0 1 1 but we don't have this 0 so what we can do is where we were 0 0 1 so what we have to do 0 0 1 and then double 0 double 1 so we will make a transition like this q3 to q1 for 0 right I hope you go at this point and then 0 1 1 so we are done with this string now 0 0 1 0 0 1 1 yes we are done with this string so now let us come to a fifth string our fifth string is double 0 double 1 doubles ero double one so double 0 double 1 yes we have it and then we want double 0 double 1 we have 0 1 1 but we do not have this 0 so we can make a transition from set q4 to q1 for the 0 so for 0 we have made this transition 0 and then 0 1 1 so we are completed with this string as well so now we have completed with all the strings so over step 3 is also completed so now let us apply our step 4 our step 4 is we have to send all the left possible combinations to the starting state right so let us check our states one by one for state Q naught or Q 0 we have a transition for 0 but we do not have a transition for 1 so we will make a transition for one like this right and then for Q 1 we have a transition for 0 but we do not have a transition for 1 so we will make a transition for 1 like right this is the transition for one and now let us come to verse state q2 for q2 we have a transition above one as well as for 0 so thing to do so now let us come to over state q3 for q3 we have a transition for 0 for 0 as well as for 1 so nothing to do here also for state q4 we have a transition for 0 but we do not have a transition for 1 so what we can do is we have to send it to the initial state like this right so now all the states has the transition for the input alphabet 0 & 1 right so this is our final solution this is our final required DFA I hope now you are also clear with this problem right I hope by now you must have got much more clarity about how to construct the DFA for the strings ending with a particular substring right in the next video we will see how to construct the DFA for the languages containing strings and sorry starting with the particular substring here in type 1 we covered those strings which are ending with a particular substring and now in type 2 we will see the strings that starts with a particular substring right so watch part 2 for that this is all about part 1 thank you so much for watching this video and please like share and comment truly speaking I personally read all your comments and loved reading them so please give your feedback so that I can make much more videos as per your need right and yes don't forget to subscribe yourself if you haven't subscribed yet for getting the latest updates thank you so much for watching

25 thoughts on “How to construct a DFA in Automata | Shortcut Easiest Way Step by Step | Part-01

  1. After watching lots of video on dfa I found the best video on the yt. Thanks so much for uploading it.

  2. Aslamualikum.. it is great explanation of DFA in very easy Way..Thanks Alots..Dear..please also make the video on NFA and conversion NFA to DFA..

Leave a Reply

Your email address will not be published. Required fields are marked *