in this video we are going to discuss about converting nfa to dfa so nfa will be given so we have to convert that nfa into the dfa or this can also be called as equivalence of dfa and nfa so nfa will be given we have to calculate the equivalent dfa for the corresponding nfu so in this video we are going to solve these two examples first let us solve the first example design dfa from the given nfa so this is the nfa which is given in the which is the problem so we have to construct dfa for this nfa so before converting nfa into the dfa first construct state transition table for the nfa so for nfa calculate transition table transition table so let us calculate transition table for the nfa for nfa so here the initial state is q naught and the remaining states are one q two q naught is the uh initial state so we have to use arrow symbol uh q2 is the final state so place in circle and the alphabet contains two symbols zero and one so q naught on zero means uh q dot as well as q one so here we have two states are there so let us use curly brace so within the curly braces uh place the statements next q naught on one means there is no transition so if there is no transition then pi empty state next q one on zero means q one on zero means there is no transition so pi next to q1 on one means uh if it goes to the q1 state as well as q2 state so two states q1 comma q2 so we have to use curly braces so within the curly braces q1 comma q2 okay now let us see the next one next here we have q2 so q2 on zero means we will go to the q naught state q naught state next to q 2 on 1 means there is no transition so pi so this is the transition table for the nfa in the examination nfa may be given or nfa transition table may be given okay now we have to construct the dfa so for that let us calculate let us construct the transition table okay transition table for dfa so dfa transition table dfa transition table so here for this uh we have to start from the initial state here in the problem what is the initial state q naught is the initial state so q naught and alpha bit contains two symbols zero and one so q naught on zero means we will move to the q naught q one that is already given in the problem so q naught comma q one next q naught on one means we will move to the pipe we will move to the pi okay uh next here here the new states are q naught comma q one q naught comma q one is the new state it is not the whole state so the next state will become q naught comma q one the next state will become q naught comma q one why because this is the new state now let us calculate the transition function so delta of delta of q naught comma q 1 comma 0 let us apply 0 on q naught q one so we can write this as delta of q naught comma zero union delta of q one comma zero what is q naught comma zero q naught comma q one q naught comma q 1 union what is q 1 comma 0 pi fine so q naught comma q 1 union pi is nothing but q naught comma q 1 only so here the here we have more than one state is there so enclosed within the curly braces likewise calculate uh by applying the input symbol one so delta of delta of q naught comma q one comma one so this can be written as delta of q naught comma 1 union delta of q 1 comma 1 delta of q naught comma 1 comma union delta of q 1 comma 1 ok so q naught comma 1 means pi union q 1 comma 1 means q 1 q 2 q 1 q 2 okay so pi q 1 q 2 so pi union q 1 q two is nothing but q one q two only so q one q two only so here q naught comma q one state is processed next to pi there is no need to process pi okay why because that is the empty state so the first row is over now let us observe the next one q naught comma q one q naught comma q one is already explored so there is no need to explore that state one more time okay exploring the node once that is enough next q1 comma q2 okay so this is the new state this this is not explored till now okay so the next state is q1 comma q2 q1 comma q2 so first we have to calculate delta of q1 comma q2 comma 0 here this is the q1 this is the q2 so if we apply 0 on q1 then we will get pi if we apply 0 on q2 we will get q naught so pi union q naught means what q naught so here we have only one state is there so there is no need of any calibrace next one q 1 comma q 2 comma 1 q 1 comma q 2 comma 1 so that means q 1 comma q to union pi so that is nothing but q one comma q two only q one comma q two only okay uh now let us check if there are any new states or not so q one comma q two is processed that is explode next to q naught q naught is already explored already it is processing next q one comma q two it is already processing so all the states are explored so with this we can conclude that transition table is over now according to the transition table we have to construct the dfa so here for space constraints i'm erasing this project let us construct the transition table here dfa means if the input alphabet contains two symbols then each state must consume those those two symbols but here we have pi is there pi is there so pi means empty state so for that purpose here let us assume the state as qd so d stands for dead state why because here this is the dfa dfa means each state must consume the symbols the symbols 0 and 1 but if we apply 1 on q naught we are moving to the pi empty state so that's why let us assume that this is qd so dead state dead state so here what is the final state in the problem q naught is given as the initial state as well as final state only okay so now the states which contains q naught will become the final state if we observe the first state q naught so q naught is nothing but final state only so q naught is now initial state as well as final state if we observe the second one q naught comma q one so the second state contains q naught so the state will also become the final state if we observe q one comma q two so q q1 comma q2 there is no q naught so this is not the final state so let us construct the transition table so q naught q naught is the transition table q naught is the initial state and the next state is what q naught comma q one next state is q naught comma q uh while drawing the corresponding dfa it is better to use square bracket instead of curly braces let us use square bracket if if we use curly braces also there is no problem but it is better to write square bracket it is better naming convention so q naught comma q one this is the second state and the next state is q1 comma q2 next state is q1 comma q2 and the last state is qd qd qd okay so here what are the final states q naught is the final state as well as q naught comma q one is the final state okay so q naught on zero means q naught q one q naught on zero means q naught q one q naught on one means dead state q naught and one means dead state next q naught q one on zero means same so self loop q naught q one on one means q1 q2 q1 q2 okay here we have to use double circles why because this is the final state this is normal state only so q naught q 1 on 1 means q one q two one means q one q two we know how to write a state state means use circuit whereas if it is a final state then use double circle here q naught q naught q one are the final states so that's why we used uh double circles next q one q two on zero means q naught q one q two on zero means q naught next q one q two on one means same state so this is the dfa for this nfa in this way we can solve the problem now let us solve one more example so that if there are any doubts then those doubts will get clarified so we have to construct dfa for this nfa the nfa is like this so q naught is the initial state q naught on a comma b means q naught q naught on a means q one q one on b means we will get q two q two so this is the uh nf here so first calculate transition table calculate transition table for this nfa once transition table of nfa is calculated then directly we can calculate dfa transition table without calculating the transition functions delta of q naught comma zero but there is no need to calculate directly from this one we can write so here q naught is the initial state and the next states are q one q two what is the final state q two is the final state okay so q naught on a means u naught state as well as q one state so here the alphabet contains two symbols q naught on a means q naught comma q one q naught on b means q naught only next q1 on a means there is no transition so empty state pi q1 on b means q2 only one state so no need of any calibres for q2 there is no transition so q2 on a means by q2 and b means pi now let us calculate dfa transition table dfa transition table so always we have to start from the initial state here what is the initial state q naught is the initial state and the alphabet contains two symbols a b so q naught on a means q naught q one q naught and b means q naught q naught so next we have to check whether these states are new states or bold states here q naught comma q one is the new state so let us explore q naught comma q one so q naught q one on a means q naught q one on a means q naught on a means q naught q one q one on a means pi so q naught comma q one union pi means q naught comma q one next q naught comma q one on b means q naught on b means q naught q one on b means q two so q naught comma q two means q naught union q two means q naught comma q two so q naught comma q one state is explode next to q naught q naught is already processed it is bold state only so there is no need to process one more time next q naught comma q one it is already processor so next to q naught comma q two this is the new state so let us explore q naught comma q two so q naught comma q two on a means q naught comma q one and pi so we'll get q naught comma q 1 only next q naught comma q 2 and b means q naught comma pi so q naught comma pi means q naught only so here we have only one state so curly braces are not needed so q naught comma q two is over now let's check the next state q naught q one this is world state only next to q naught this is whole state only so with this we can conclude that transition table is lower now according to the transition table let us construct the dfa so what are the states here q naught q naught is the initial state what at what is the final state here in the problem q 2 is the final state so the states which contains q 2 will become the final state so here we have only one state which contains q2 so this state will become the final state so q naught so next state is q naught comma q 1 next q naught comma q 2 this is the final state so let us use square bracket let us use brackets instead of curly braces brackets are better so q naught comma shu one q naught comma q next to q naught comma q two q naught comma q two this is the final state so final state means we have to use double circles here there is no need to use q d why because here we don't have pi if there is pi then only we have to use qd so q naught on a means q naught q one q naught on b means q naught self loop q naught q one on a means u not q one only self loop q naught q one on b means q naught q two q naught q two on a means q naught q one q naught q 2 on b means q naught so this is the dfa for the given nf here so in this way we can convert nfa into the dfa