Note | Coconote

[Music] [Music] hello everyone and welcome back to the lecture series of learning theory of automata and formal languages my name is binayak parashar i am working as an assistant professor in the department of computer science and engineering at ajay kumar garg engineering college khaziabad ah we have been continuing with this lecture series and this is the fifth lecture and ah in the past lectures we have seen the basic introductions to automata theory we have seen the basic terminologies like alphabets strings languages okay powers then length and based on that we have tried to analyze ah the concept of finite automata and we have also tried to ah learn almost 10 to 11 examples on how to design the the the concept of deterministic finite automata and based on that we will be continuing with our lecture and let us check it out that what is our today's agenda so today's agenda is we have we are going to learn about non-deterministic finite automata in short form it is nfa and also we will try to look into the concept of equivalence of d f n n f e ok so this is the basic topics that we are going to cover up we will try to design nfa and then we will try to look into the equivalence property of dfn nfa ok so somebody other we will try to look into the concept of ah like like like no restriction part on the concept of finite automata till now we have seen certain restrictions that we are having in finite automata which is named as deterministic finite automata but in here we will not go with the restrictions part we will just go on accepting the language thats it ok so lets check it out so what is the basic ah like basic preliminary terminologies that we are having regarding non deterministic finite automata is that first point is that the transition from a state the transition from a state can be to a multiple naked states so these point is only the most important point to understand in the case of nfa lets check a little bit of difference between d f and f a then it will be much clearer to you all ok so lets take suppose i am having a state and i am having one more state and lets suppose this is the final state ok i am not naming the nomenclature of these states just i am designate this the particular two states we are having ok one is your in a let let me say that this is an initial state suppose ok and i am concentrating only one input symbol say a ok for this input symbol a this particular state will have a transition to this particular final state ok or it may be like this ok or it may be like this this particular initial state i have made as a final state and i have done a transition of a or you can say a loop of a onto this on to the onto itself ok now if you look in these two scenarios if we look in these two scenarios we are having exactly one transitions which is going from one state to another state or to itself which is the definition of what dfa that means you can say one to one one to one you can ah like you can understand in a better way like suppose if i want to ah omit this particular concept and i want to do one too many concept that means for a single input alphabet i can do not one to one i can do one to many ok so that concept belongs to nfa ok so if i erase this particular thing ok and if i write simply a state q naught say suppose and i am having a state suppose q 1 i am having a q 2 i am having a q 3 ok and in all these states i am having one one transitions each and also i am having a self loop and in all these transitions i am having an input symbol a so this can be possible only in the case of nfa one too many transitions can be done ok what is the main concept of nfa is that it is required only to accept the language it does not have any kind of restriction that for only a single input alphabet or whatever input alphabet is there there will be exactly one transition not more than that not less than that ok that is not present in the case of nfa i hope you have understood the concept of dfn nfa difference now let us move into the second point non deterministic automaton yes as i have already told it it is not determined that there should be exactly one transition so the name came non determinism or non deterministic automaton then ndfa permits empty string transitions see as there is no restriction so ndfa or nfa both are same can have empty transitions also like this suppose i am having one more state say suppose q f and i can have an empty transition ok an empty transition this means that i can i there is nothing string between q naught and q f but yes i can have a string which is having length equals to zero so that is known as m t ok so this is a basic terminologies about nfa let us go to the definition of nfa formal description of nfa if you have understood in the previous video we have discussed about the formal description of dfa we have this we have discussed about formal description of fa also finite automata exactly same only the difference lies here that is the transition function ok now as you have seen into the previous slide previous slide says that from one transition from one state it can have multiple transitions that means how i can write down i can write down that the total number of states involved should be should be correspond to the number of input alphabets so here i am concentrating only a it may be a it may be it may be many many alphabets right and it should go to not a single state it should go to two to the power q ok two to the power q got it so this is what the meaning two to the power q means its not a single state it can go to n number of states ok now if you look into the transition function transition function says the same that q ah correspond to the number of input alphabets it will go to 2 to the power q number of states ok so this is the general difference between the formal description of df and nfa restart everything is safe it is a finite number of say states finite number of input input alphabets initial state final state ok so now let us go to the next concept the next concepts come ah is ask about the graphical representation of nfa ok graphical representation of nfa so if we have understood in the previous example in the previous lecture video where we have understood the graphical representation of dfa its exactly the same no changes are there ok only one change is there that i have already told you is empty transitions are there ok so lets go into the upcoming ah slide here we will here we will start off with like discussing the numerical part so we have taken almost the same language which we have discussed in the previous video while designing the construction of dfa the same examples we will take and we will try to look into the difference between that because to my point of view if you have understood dfan if you have practiced almost 30 questions then there is no like not required for you to like practice for the for nfa also ok so lets check it out few questions so constructor ok fine this is not a df it is nfa ok construct an nfa over ah given alphabet so we are having a and b ok where the length is equals to 2 length is equals to 2 you can if you have not seen my previous video then please look into the previous video we have discussed about the length ah and how to calculate the language for the same ok so therefore i am summing up and we got the language as this one l is equals to a a a b b a b b ok now what we need to construct we need to design a finite automata in such a whether all the strings gets accepted which is the fun which is the concept of nfa so what i will do i will take an initial state say suppose a i will take one more state say suppose b and i will take one more states say suppose c ok first i will check for this string so first one is what a done second element is what a so a a finally it is accepted ok always remember this a a means a dot a ok we will discuss this concept in unit number 2 while we will discuss about regular expression ok but as of now when we are having two alphabets together that means it is deviated by through through states ok you cannot put these two concepts these two alphabets together in the same transition ok so therefore we got a a now we can now this is done now we will check a b a b b is not there so i will put a b transition over here which we have discussed in the previous examples also previous lecture b a so b is not present so i can do a b transition from the initial state so b a is done this is also accepted if i look into b b b b its present now if i check it out over here everything is done all the strings gets accepted and we have drawn the finite out of beta and this is your required nfa so there is no restriction we have tried to follow the the the acceptance of the strings which is being done so we can stop here and we can describe that this is the final automata or which we can say final nfa for the given language ok so if you have any if you are drawing a d effect and we would have required one more transition because c does not have any kind of transition for both the input symbols correct so i have to draw a ah like one more transition if we have gone for dfa for it but here we are designing nfa we are done with the language part we have the language all the strings have been accepted so we can stop here and this is the final diagram clear let us go with the next question ok let me first delete this and i have shown you the graphical part so the graphical part will look like this a will come then one more state b then one a single a transition we will got it then one more state i will take that is c which i have made as a final state and then a then similarly a for a b i will take one ah this one b transition for b a i will take one more transition and for b b i will take one more transition so that means overall i got a b a b ok which i take a a means a a a b means a b then b a means b a then b b means b b ok we got all the transitions done got it next comes the next question ok example number two it says design a finite automata that accepts strings containing 0 1 0 as the substring now let us take the language first in the language if we look into properly then what is the preliminary string that you can have it it says that now please ah like do not try to focus in this particular first part because it is asking designer finite automata finite automata can be nfa can be dfa so you can make any one of them but as of now we are discussing about nfe only so we will try to look into the nfa concept online ok now it says design a finite automata that accepts strings containing 0 1 0 as a substring ok now if we have to look into this then what is the initial string that we need to take it initial string will be 0 1 0 correct it says that for every string which is present in the language a sub string should be present which is nothing but 0 1 0 always so that means if we take 0 1 0 as a substring of that particular language this is also an accepted by the language correct now if we talk about any more further language suppose 0 1 0 i have taken earlier it can be 2 0's later on it can be 2 ones it is possible right i need to check that whether 0 1 0 is present as a substring or not in every strings correct i can take like this 1 1 1 1 1 then 0 1 0 0 yes it is present it can be like one zero one zero zero one zero zero zero yes zero one zero is present ok so you need to check that whether containing zero one zero is a substring is present or not so it will keep on going till infinite so i got some many other few strings in your examination you try to put at least 10 to 15 ah string so that you can analyze the particular language and you can put down or you can draw the or you can design the particular diagram here so let us check the diagrammatic part of it so i need to take first of all always if you having questions like this where there is a part of a restriction you try to design that restriction part first ok that means 0 1 0 is the restriction part so i will try to design this 0 1 0 at first and then i will try to analyze what no left part we are having ok so i will try to design the first initial part that is 0 1 0. so i am having 0 i am having 1 i am having 0 and this will be reached due to wood final state so i have taken this as the final state this is suppose c these are the names of the states ok so 0 1 0 is accepted now somewhere the other i am satisfied that yes my restriction part has been done i need to focus on my remaining maximum number of possible strings so can can you can like think of what you can do like posit like pause the video and you can think of it that can we start over here with either 0 or 1 yes i can start right because 0 1 0 before that it can have n number of possible combinations of 0 and 1 right so that is why i have taken a self loop at the initial state ok thereafter it will have 0 1 0 i will not put anything between them let it be together ok we cannot separate them so next what i can do can i take a self loop over here in order to like have a n number of possible combinations of 0 and 1 over here yes i can take it got it so that i can have maximum possible combinations now if you can analyze properly starting with 0 and 1 possible combinations it can have an any number followed by 0 1 0 it needs to reach to the final state in order to accept the string right so 0 1 0 will be reached to the final state we are done possibly we might have after 0 1 0 we might have zero and one possible combinations right so i have taken a self loop over here so this is the final diagram of the nfa why i have declared that this is a final because i am done with the language part and i can disclose that yes everything has been done ok now if we look into this concept we have mentioned here example of transition table for nfa so i have designed and you have in the previous video we have seen about how to design a transition table the same way you are going to design a transition table over here how to do that simply ok ah in the columns will be having the inputs that is 0 and 1 ok that is nothing but inputs and in the rows we will be having the states so how many states we are having we are having a as the initial state b c and one more is there f so f being the final state so these are the states we are having now we just need to compare the transitions a on sync 0 it is going to c now a on sync 0 it is going to a as well as b so i will take like this a comma b this is very important to understand ok a on sync one where it is going it is going to itself so i will take a b on sing 0 b on sing 0 anywhere any transitions no transitions that means it will be phi b on seeing ah one it is going to state c c on sink zero it is going to capital letter f c on sink one is there any transition going out form c no transition that means it will be phi then f on sing 0 and 1 it is going to itself so it will be f so this is the transition table for the given nfa got it so i am done with this example i hope it is clear to everyone lets go with the third question third question also its very similar we have done this question in the previous video so you can refer to that video the diagram was similar i have mentioned previous time also the diagram was similar it was like this multiples of three means what the language will comprise land three then length six then length nine and it will keep on going right so the diagram was like this if you remember if you have practiced the d f equation so a and b right so a ok 3 times a then if i get 6 times a then i will be getting over here so everywhere i can give a comma b a comma b a comma b so if you look into this diagram it will be having lens 3 6 9 ah then 12 then 15 eighteen and it will keep on going it will take all the multiples of three as well as divisible by three as well ok so you practice you try to practice this question now if you look into this question we are done with the language part and if you look into the scenario it is also dfa it is also nf ok you can if you have understood both the videos then you will be able to understand this concept also now let us go with the next question next question says that design a finite automata with the input symbol except those strings which starts with one and ends with zero so my language will be what starts with one and ends with zero so the preliminary string the basic string will be what one zero why starts with one ends with zero try to design this first a one zero ok so i got this particular diagram where starting with one and ending with zero clear now if we look into the scenario can one and zero in between that we have you can have an n possible number of strings yes so what i can do i can take a self loop and i can give one comma zero its an nfa it does not have any kind of restriction so you can put anywhere or just need to just satisfy the language so one zero is done now anything we can do it in order to satisfy if you want you can also put over here as zero so this will work starting with one ending with zero somebody other zero will end on the final state only now if you want to give here starting as one you can give it its completely dependent on you if it does not give to these scenarios also doesn't it will not hamper your diagram why because it will start with one it will end with a zero and some of the other in between that all possible combinations of one zero are possible correct entirely infinite all possible combinations so why to use one more ah loop over here and one more loop over here it will not be an ah like an optimized diagram right so the summary other you can remove these two loops if you want so this is all about your the example number four i have also draw drawn over here the diagram ok now if you go back to the diagram you can let you can check it out ok now come to the last topic of today's session that is the equivalence of dfn nfa now if you talk about this particular topic till now we have seen nfa we have seen dfa now we might have a question that as nfa and efa both are same finite automata having some sort of restrictions between both of them can they accept the same language yes they can accept the same language because they belong to the same domain ok whatever language has been accepted by nfa will be accepted by dfa so this is a very important point keep in mind so if we look into the expressive power of both nfas and efa we will and we will understood this particular topic see first point says that is there a language that is recognized by dfa but not by nfa no all languages which is accepted by dfa as well as it will be accepted by nfa also if you look into the second point the second point says the same concept that is recognized by nfa but not recognized by df it is not possible so this is also no so therefore a language l is recognized by dfa if and only if there is an nfa such that the language of nfa should be equals to the language of tfa which is the mis basic ah like you can say abstract of this particular topic so if a language accepted by dfa it will be accepted by nfa so that is what the summary of this particular topic now we need to first focus on this particular pointer the question comes that what when we will discuss about the equivalence of dfn nfa is it possible that we can convert nfa to dfa or is it possible to convert a dfa to nfa ok now before that i have asked you in the previous to previous video that whether all nfas are dfa or whether all dfas are nfa so you might have got this answer but i will not sum up this answer until we finish it up with this particular topic so in the next video i will discuss with you all but let us go with the question part and let us check how to convert a nfa to a dfa later on i will tell you why we cannot convert a dfa to nfa or why like some like some problem is there with it we will discuss in the next video but lets check how to convert a df nfa to a dfa now the given question is this one that ah what construct an equivalent dfa from the following transition table how did i got to know that this is an nfa because for input symbol b it is having multiple states for this input symbol ok for the sorry for the state b for the input symbol 0 it is having multiple state transitions so that means it is not possible that is a dfa apart from that is there any kind of ah yeah one more state is there ok apart from that if you find ah phi also then also it will be you will be able to know that is an nfa diagram ok how to draw this we need to take a transition table for this ok 0 and 1 ok i will let you know the final steps but how to do it right now this is what this is the transition table for nfa ok and this is what this is the transition table for d f a ok so first step is that you need to convert this transition table of d and f a to transition table of dfa how to do that please listen very carefully the nfa transition table in the first row whatever is there write down exactly over here so what it will be a a b now if we look into this particular row for which state you are looking into this diagram you are looking for the state a so now you need to scan this row and you need to check is there any new state apart from a yes we got b so bring those bring this b to the next row clear so i now i will be checking for b if you look into b transition in the b transition i am having what i am having b c on sync 0 and b on sing 1 so write down as it is so b c and b now look into the second row in the second row while we are checking for the state b is there any new state that is coming yes a new state it is coming that is your b c now you might be having a question that b and c are two different states so why we are talk taking as an as a single turn state yes we need to comb whenever whenever we are looking for b and going for 0 and it is going for b and c state board so together we have to take as a single state clear so now we need to bring this state over here b and c and we need to check how how we need to check this now look into the transition table of nfa on sync b and c together on sync 0 it is going to where b comma c and c so c and c are same so b c so therefore it will be b and c you can rewind the play and you can just like revise this topic see again i will check for input symbol one on sync b and c it is going to where b and b c b and b are same so it will be b c therefore is there any new state in the last column last row no once you are done with finding all the new state ok ah like you are not getting any new state then you have to stop here and that will be the final transition table for the tfa so therefore if you look into this particular table which will be the final state this one why because c was the final state and now c is merged with b so therefore b c will be taken as a final state clear so overall this is the transition table for dfa and if you want to draw the diagram for this yes we can draw that how to draw it ok we can draw like this so i will be having one state as a initial state i will be having b as the next state and i will have b c as the final state ok so a on sync 0 where it is going it is going to itself a on sing 1 where it is going to be b on sync 0 it is going to b c b on sin one where it is going it is going to itself b c on seeing zero and one both are going to itself only so this is the final diagram of the d f a ok so if a question comes that construct an equivalent dfa for the given diagram or construct a final or you can say or construct a dfa from the given diagram so first of all if the diagram is given to you that is transition diagram is given to you you need to convert that transition diagram of nfa to transition diagram or transition table of nfa from that the tape the the process is this one transition table of dfa and transition diagram of df so this is the conversion process of nfa to dfa i hope it is clear to everyone so lets ah look into the next example the next example says find the equivalent dfa for the following machine now if you do a little bit fast what will be the table first i will try to design the table for the nfa ok zero and one ok now if we look into the states q naught is the initial state ok then q one and q two q two is the final state ok so q naught on sync zero where it is going it is going to itself q naught on seeing one it is going to q one ok q one on sing zero it is going to itself and to q two so it will be what will be what is the answer q one comma q two ok now same way q one on seeing one it is going to itself and wherever it is going no it is not going in so it will be q one q two on sing zero it is coming to itself and anywhere it is going no it is going to itself then q two on seeing one it is coming to itself and going to q one so therefore the answer will be q two comma q one or q one comma q two anything ok so therefore this is the table that you got this is the transition table for nfa now you need to convert this transition table to the given dfa ok so this is how you need to do it so after that you just try to do it on your own and you will be getting the answer like this ok so you will be getting first you will be having the row as same row as as it is so q naught q naught q one ok now if you look into this particular row what is the new state that you got q one bring it over here now let us check for q one q one i got it as q one q two and here it will be q one correct what is the new state that you have got q one q two ok so if you look into q one and q two it is coming as q one q two q two so it will be q one q two only ok and if we look into this one next one it will be q one q two only so that means the diagram is somewhat similar to the previous one ah that we have discussed but i have shown you how to draw it first the transition diagram will be given to you from that you need to convert this to transition table for nfa then transition table for dfa then transition table diagram for dfa so this is the way you need to do a equivalence of dfa or nfo nf a to dfa ok so in the next video we will come across with one more interesting topic and i will discuss this particular pointer i have asked you that whether all dfas are nfa or all nfs are dfa so next topic we will discuss about the epsilon transition for nfa keep watching this videos thank you

[Music] [Music] hello everyone and welcome back to the lecture series of learning theory of automata and formal languages my name is binayak parashar i am working as an assistant professor in the department of computer science and engineering at ajay kumar garg engineering college khaziabad ah we have been continuing with this lecture series and this is the fifth lecture and ah in the past lectures we have seen the basic introductions to automata theory we have seen the basic terminologies like alphabets strings languages okay powers then length and based on that we have tried to analyze ah the concept of finite automata and we have also tried to ah learn almost 10 to 11 examples on how to design the the the concept of deterministic finite automata and based on that we will be continuing with our lecture and let us check it out that what is our today&#39;s agenda so today&#39;s agenda is we have we are going to learn about non-deterministic finite automata in short form it is nfa and also we will try to look into the concept of equivalence of d f n n f e ok so this is the basic topics that we are going to cover up we will try to design nfa and then we will try to look into the equivalence property of dfn nfa ok so somebody other we will try to look into the concept of ah like like like no restriction part on the concept of finite automata till now we have seen certain restrictions that we are having in finite automata which is named as deterministic finite automata but in here we will not go with the restrictions part we will just go on accepting the language thats it ok so lets check it out so what is the basic ah like basic preliminary terminologies that we are having regarding non deterministic finite automata is that first point is that the transition from a state the transition from a state can be to a multiple naked states so these point is only the most important point to understand in the case of nfa lets check a little bit of difference between d f and f a then it will be much clearer to you all ok so lets take suppose i am having a state and i am having one more state and lets suppose this is the final state ok i am not naming the nomenclature of these states just i am designate this the particular two states we are having ok one is your in a let let me say that this is an initial state suppose ok and i am concentrating only one input symbol say a ok for this input symbol a this particular state will have a transition to this particular final state ok or it may be like this ok or it may be like this this particular initial state i have made as a final state and i have done a transition of a or you can say a loop of a onto this on to the onto itself ok now if you look in these two scenarios if we look in these two scenarios we are having exactly one transitions which is going from one state to another state or to itself which is the definition of what dfa that means you can say one to one one to one you can ah like you can understand in a better way like suppose if i want to ah omit this particular concept and i want to do one too many concept that means for a single input alphabet i can do not one to one i can do one to many ok so that concept belongs to nfa ok so if i erase this particular thing ok and if i write simply a state q naught say suppose and i am having a state suppose q 1 i am having a q 2 i am having a q 3 ok and in all these states i am having one one transitions each and also i am having a self loop and in all these transitions i am having an input symbol a so this can be possible only in the case of nfa one too many transitions can be done ok what is the main concept of nfa is that it is required only to accept the language it does not have any kind of restriction that for only a single input alphabet or whatever input alphabet is there there will be exactly one transition not more than that not less than that ok that is not present in the case of nfa i hope you have understood the concept of dfn nfa difference now let us move into the second point non deterministic automaton yes as i have already told it it is not determined that there should be exactly one transition so the name came non determinism or non deterministic automaton then ndfa permits empty string transitions see as there is no restriction so ndfa or nfa both are same can have empty transitions also like this suppose i am having one more state say suppose q f and i can have an empty transition ok an empty transition this means that i can i there is nothing string between q naught and q f but yes i can have a string which is having length equals to zero so that is known as m t ok so this is a basic terminologies about nfa let us go to the definition of nfa formal description of nfa if you have understood in the previous video we have discussed about the formal description of dfa we have this we have discussed about formal description of fa also finite automata exactly same only the difference lies here that is the transition function ok now as you have seen into the previous slide previous slide says that from one transition from one state it can have multiple transitions that means how i can write down i can write down that the total number of states involved should be should be correspond to the number of input alphabets so here i am concentrating only a it may be a it may be it may be many many alphabets right and it should go to not a single state it should go to two to the power q ok two to the power q got it so this is what the meaning two to the power q means its not a single state it can go to n number of states ok now if you look into the transition function transition function says the same that q ah correspond to the number of input alphabets it will go to 2 to the power q number of states ok so this is the general difference between the formal description of df and nfa restart everything is safe it is a finite number of say states finite number of input input alphabets initial state final state ok so now let us go to the next concept the next concepts come ah is ask about the graphical representation of nfa ok graphical representation of nfa so if we have understood in the previous example in the previous lecture video where we have understood the graphical representation of dfa its exactly the same no changes are there ok only one change is there that i have already told you is empty transitions are there ok so lets go into the upcoming ah slide here we will here we will start off with like discussing the numerical part so we have taken almost the same language which we have discussed in the previous video while designing the construction of dfa the same examples we will take and we will try to look into the difference between that because to my point of view if you have understood dfan if you have practiced almost 30 questions then there is no like not required for you to like practice for the for nfa also ok so lets check it out few questions so constructor ok fine this is not a df it is nfa ok construct an nfa over ah given alphabet so we are having a and b ok where the length is equals to 2 length is equals to 2 you can if you have not seen my previous video then please look into the previous video we have discussed about the length ah and how to calculate the language for the same ok so therefore i am summing up and we got the language as this one l is equals to a a a b b a b b ok now what we need to construct we need to design a finite automata in such a whether all the strings gets accepted which is the fun which is the concept of nfa so what i will do i will take an initial state say suppose a i will take one more state say suppose b and i will take one more states say suppose c ok first i will check for this string so first one is what a done second element is what a so a a finally it is accepted ok always remember this a a means a dot a ok we will discuss this concept in unit number 2 while we will discuss about regular expression ok but as of now when we are having two alphabets together that means it is deviated by through through states ok you cannot put these two concepts these two alphabets together in the same transition ok so therefore we got a a now we can now this is done now we will check a b a b b is not there so i will put a b transition over here which we have discussed in the previous examples also previous lecture b a so b is not present so i can do a b transition from the initial state so b a is done this is also accepted if i look into b b b b its present now if i check it out over here everything is done all the strings gets accepted and we have drawn the finite out of beta and this is your required nfa so there is no restriction we have tried to follow the the the acceptance of the strings which is being done so we can stop here and we can describe that this is the final automata or which we can say final nfa for the given language ok so if you have any if you are drawing a d effect and we would have required one more transition because c does not have any kind of transition for both the input symbols correct so i have to draw a ah like one more transition if we have gone for dfa for it but here we are designing nfa we are done with the language part we have the language all the strings have been accepted so we can stop here and this is the final diagram clear let us go with the next question ok let me first delete this and i have shown you the graphical part so the graphical part will look like this a will come then one more state b then one a single a transition we will got it then one more state i will take that is c which i have made as a final state and then a then similarly a for a b i will take one ah this one b transition for b a i will take one more transition and for b b i will take one more transition so that means overall i got a b a b ok which i take a a means a a a b means a b then b a means b a then b b means b b ok we got all the transitions done got it next comes the next question ok example number two it says design a finite automata that accepts strings containing 0 1 0 as the substring now let us take the language first in the language if we look into properly then what is the preliminary string that you can have it it says that now please ah like do not try to focus in this particular first part because it is asking designer finite automata finite automata can be nfa can be dfa so you can make any one of them but as of now we are discussing about nfe only so we will try to look into the nfa concept online ok now it says design a finite automata that accepts strings containing 0 1 0 as a substring ok now if we have to look into this then what is the initial string that we need to take it initial string will be 0 1 0 correct it says that for every string which is present in the language a sub string should be present which is nothing but 0 1 0 always so that means if we take 0 1 0 as a substring of that particular language this is also an accepted by the language correct now if we talk about any more further language suppose 0 1 0 i have taken earlier it can be 2 0&#39;s later on it can be 2 ones it is possible right i need to check that whether 0 1 0 is present as a substring or not in every strings correct i can take like this 1 1 1 1 1 then 0 1 0 0 yes it is present it can be like one zero one zero zero one zero zero zero yes zero one zero is present ok so you need to check that whether containing zero one zero is a substring is present or not so it will keep on going till infinite so i got some many other few strings in your examination you try to put at least 10 to 15 ah string so that you can analyze the particular language and you can put down or you can draw the or you can design the particular diagram here so let us check the diagrammatic part of it so i need to take first of all always if you having questions like this where there is a part of a restriction you try to design that restriction part first ok that means 0 1 0 is the restriction part so i will try to design this 0 1 0 at first and then i will try to analyze what no left part we are having ok so i will try to design the first initial part that is 0 1 0. so i am having 0 i am having 1 i am having 0 and this will be reached due to wood final state so i have taken this as the final state this is suppose c these are the names of the states ok so 0 1 0 is accepted now somewhere the other i am satisfied that yes my restriction part has been done i need to focus on my remaining maximum number of possible strings so can can you can like think of what you can do like posit like pause the video and you can think of it that can we start over here with either 0 or 1 yes i can start right because 0 1 0 before that it can have n number of possible combinations of 0 and 1 right so that is why i have taken a self loop at the initial state ok thereafter it will have 0 1 0 i will not put anything between them let it be together ok we cannot separate them so next what i can do can i take a self loop over here in order to like have a n number of possible combinations of 0 and 1 over here yes i can take it got it so that i can have maximum possible combinations now if you can analyze properly starting with 0 and 1 possible combinations it can have an any number followed by 0 1 0 it needs to reach to the final state in order to accept the string right so 0 1 0 will be reached to the final state we are done possibly we might have after 0 1 0 we might have zero and one possible combinations right so i have taken a self loop over here so this is the final diagram of the nfa why i have declared that this is a final because i am done with the language part and i can disclose that yes everything has been done ok now if we look into this concept we have mentioned here example of transition table for nfa so i have designed and you have in the previous video we have seen about how to design a transition table the same way you are going to design a transition table over here how to do that simply ok ah in the columns will be having the inputs that is 0 and 1 ok that is nothing but inputs and in the rows we will be having the states so how many states we are having we are having a as the initial state b c and one more is there f so f being the final state so these are the states we are having now we just need to compare the transitions a on sync 0 it is going to c now a on sync 0 it is going to a as well as b so i will take like this a comma b this is very important to understand ok a on sync one where it is going it is going to itself so i will take a b on sing 0 b on sing 0 anywhere any transitions no transitions that means it will be phi b on seeing ah one it is going to state c c on sink zero it is going to capital letter f c on sink one is there any transition going out form c no transition that means it will be phi then f on sing 0 and 1 it is going to itself so it will be f so this is the transition table for the given nfa got it so i am done with this example i hope it is clear to everyone lets go with the third question third question also its very similar we have done this question in the previous video so you can refer to that video the diagram was similar i have mentioned previous time also the diagram was similar it was like this multiples of three means what the language will comprise land three then length six then length nine and it will keep on going right so the diagram was like this if you remember if you have practiced the d f equation so a and b right so a ok 3 times a then if i get 6 times a then i will be getting over here so everywhere i can give a comma b a comma b a comma b so if you look into this diagram it will be having lens 3 6 9 ah then 12 then 15 eighteen and it will keep on going it will take all the multiples of three as well as divisible by three as well ok so you practice you try to practice this question now if you look into this question we are done with the language part and if you look into the scenario it is also dfa it is also nf ok you can if you have understood both the videos then you will be able to understand this concept also now let us go with the next question next question says that design a finite automata with the input symbol except those strings which starts with one and ends with zero so my language will be what starts with one and ends with zero so the preliminary string the basic string will be what one zero why starts with one ends with zero try to design this first a one zero ok so i got this particular diagram where starting with one and ending with zero clear now if we look into the scenario can one and zero in between that we have you can have an n possible number of strings yes so what i can do i can take a self loop and i can give one comma zero its an nfa it does not have any kind of restriction so you can put anywhere or just need to just satisfy the language so one zero is done now anything we can do it in order to satisfy if you want you can also put over here as zero so this will work starting with one ending with zero somebody other zero will end on the final state only now if you want to give here starting as one you can give it its completely dependent on you if it does not give to these scenarios also doesn&#39;t it will not hamper your diagram why because it will start with one it will end with a zero and some of the other in between that all possible combinations of one zero are possible correct entirely infinite all possible combinations so why to use one more ah loop over here and one more loop over here it will not be an ah like an optimized diagram right so the summary other you can remove these two loops if you want so this is all about your the example number four i have also draw drawn over here the diagram ok now if you go back to the diagram you can let you can check it out ok now come to the last topic of today&#39;s session that is the equivalence of dfn nfa now if you talk about this particular topic till now we have seen nfa we have seen dfa now we might have a question that as nfa and efa both are same finite automata having some sort of restrictions between both of them can they accept the same language yes they can accept the same language because they belong to the same domain ok whatever language has been accepted by nfa will be accepted by dfa so this is a very important point keep in mind so if we look into the expressive power of both nfas and efa we will and we will understood this particular topic see first point says that is there a language that is recognized by dfa but not by nfa no all languages which is accepted by dfa as well as it will be accepted by nfa also if you look into the second point the second point says the same concept that is recognized by nfa but not recognized by df it is not possible so this is also no so therefore a language l is recognized by dfa if and only if there is an nfa such that the language of nfa should be equals to the language of tfa which is the mis basic ah like you can say abstract of this particular topic so if a language accepted by dfa it will be accepted by nfa so that is what the summary of this particular topic now we need to first focus on this particular pointer the question comes that what when we will discuss about the equivalence of dfn nfa is it possible that we can convert nfa to dfa or is it possible to convert a dfa to nfa ok now before that i have asked you in the previous to previous video that whether all nfas are dfa or whether all dfas are nfa so you might have got this answer but i will not sum up this answer until we finish it up with this particular topic so in the next video i will discuss with you all but let us go with the question part and let us check how to convert a nfa to a dfa later on i will tell you why we cannot convert a dfa to nfa or why like some like some problem is there with it we will discuss in the next video but lets check how to convert a df nfa to a dfa now the given question is this one that ah what construct an equivalent dfa from the following transition table how did i got to know that this is an nfa because for input symbol b it is having multiple states for this input symbol ok for the sorry for the state b for the input symbol 0 it is having multiple state transitions so that means it is not possible that is a dfa apart from that is there any kind of ah yeah one more state is there ok apart from that if you find ah phi also then also it will be you will be able to know that is an nfa diagram ok how to draw this we need to take a transition table for this ok 0 and 1 ok i will let you know the final steps but how to do it right now this is what this is the transition table for nfa ok and this is what this is the transition table for d f a ok so first step is that you need to convert this transition table of d and f a to transition table of dfa how to do that please listen very carefully the nfa transition table in the first row whatever is there write down exactly over here so what it will be a a b now if we look into this particular row for which state you are looking into this diagram you are looking for the state a so now you need to scan this row and you need to check is there any new state apart from a yes we got b so bring those bring this b to the next row clear so i now i will be checking for b if you look into b transition in the b transition i am having what i am having b c on sync 0 and b on sing 1 so write down as it is so b c and b now look into the second row in the second row while we are checking for the state b is there any new state that is coming yes a new state it is coming that is your b c now you might be having a question that b and c are two different states so why we are talk taking as an as a single turn state yes we need to comb whenever whenever we are looking for b and going for 0 and it is going for b and c state board so together we have to take as a single state clear so now we need to bring this state over here b and c and we need to check how how we need to check this now look into the transition table of nfa on sync b and c together on sync 0 it is going to where b comma c and c so c and c are same so b c so therefore it will be b and c you can rewind the play and you can just like revise this topic see again i will check for input symbol one on sync b and c it is going to where b and b c b and b are same so it will be b c therefore is there any new state in the last column last row no once you are done with finding all the new state ok ah like you are not getting any new state then you have to stop here and that will be the final transition table for the tfa so therefore if you look into this particular table which will be the final state this one why because c was the final state and now c is merged with b so therefore b c will be taken as a final state clear so overall this is the transition table for dfa and if you want to draw the diagram for this yes we can draw that how to draw it ok we can draw like this so i will be having one state as a initial state i will be having b as the next state and i will have b c as the final state ok so a on sync 0 where it is going it is going to itself a on sing 1 where it is going to be b on sync 0 it is going to b c b on sin one where it is going it is going to itself b c on seeing zero and one both are going to itself only so this is the final diagram of the d f a ok so if a question comes that construct an equivalent dfa for the given diagram or construct a final or you can say or construct a dfa from the given diagram so first of all if the diagram is given to you that is transition diagram is given to you you need to convert that transition diagram of nfa to transition diagram or transition table of nfa from that the tape the the process is this one transition table of dfa and transition diagram of df so this is the conversion process of nfa to dfa i hope it is clear to everyone so lets ah look into the next example the next example says find the equivalent dfa for the following machine now if you do a little bit fast what will be the table first i will try to design the table for the nfa ok zero and one ok now if we look into the states q naught is the initial state ok then q one and q two q two is the final state ok so q naught on sync zero where it is going it is going to itself q naught on seeing one it is going to q one ok q one on sing zero it is going to itself and to q two so it will be what will be what is the answer q one comma q two ok now same way q one on seeing one it is going to itself and wherever it is going no it is not going in so it will be q one q two on sing zero it is coming to itself and anywhere it is going no it is going to itself then q two on seeing one it is coming to itself and going to q one so therefore the answer will be q two comma q one or q one comma q two anything ok so therefore this is the table that you got this is the transition table for nfa now you need to convert this transition table to the given dfa ok so this is how you need to do it so after that you just try to do it on your own and you will be getting the answer like this ok so you will be getting first you will be having the row as same row as as it is so q naught q naught q one ok now if you look into this particular row what is the new state that you got q one bring it over here now let us check for q one q one i got it as q one q two and here it will be q one correct what is the new state that you have got q one q two ok so if you look into q one and q two it is coming as q one q two q two so it will be q one q two only ok and if we look into this one next one it will be q one q two only so that means the diagram is somewhat similar to the previous one ah that we have discussed but i have shown you how to draw it first the transition diagram will be given to you from that you need to convert this to transition table for nfa then transition table for dfa then transition table diagram for dfa so this is the way you need to do a equivalence of dfa or nfo nf a to dfa ok so in the next video we will come across with one more interesting topic and i will discuss this particular pointer i have asked you that whether all dfas are nfa or all nfs are dfa so next topic we will discuss about the epsilon transition for nfa keep watching this videos thank you

Transcript for: