Automata theory - NFA to DFA Conversion

Non-deterministic and deterministic equivalence of languages

1. Conversion problem: PART-B NFA- DFA NFA - ε to NFA NFA- ε to DFA RE to NFA- ε DFA to RE Minimization of DFA

2. Convert the given NFA to DFA. Initial State of given NFA is {q0 } Since NFA is equivalent to DFA, Let Initial State of DFA be [q0] ----- A                   

3. Now we will obtain δ' transition for state A. δ’( A, 0)=  δ’( {q0}, 0) = {q0} =[q0]   -------- A Transition table δ’( A, 1)=  δ’( {q0}, 1) = {q1}=[q1]  -------- B ( new  state generated)  The δ' transition for state B is obtained as: δ’( B, 0)= δ’( {q1}, 0) = {q1, q2} =[q1,q2]       -------- C   δ’( B,1) = δ’( {q1}, 1) = {q1}=[q1]    -------- B  Now we will obtain δ' transition on C. δ’( C, 0) = δ’( {q1, q2}, 0)  =  δ( q1, 0) ∪  δ( q2, 0)                 = {q1, q2} ∪ {q2}                 = [q1, q2]   -------- C   δ’( C, 1) = δ’( {q1, q2}, 1)  =  δ( q1, 1) ∪  δ( q2, 1)                  = {q1} ∪ {q1, q2}                  = {q1, q2}                   = [q1, q2]  -------- C   1 →A A B B C B *C C C DFA - Transition diagram DFA - Transition table Resultant DFA

4. Can also be denoted the states as it is, without renaming as A,B,C 1 →[q0] [q0] [q1] [q1] [q1, q2] [q1] *[q1, q2] [q1, q2] [q1, q2]

5. Example 2: NFA to DFA Note : use [ ] in DFA instead { }

6. Example 3: NFA to DFA Resultant: State / Alphabet 1 → q0 q0 {q1, q2} State / Alphabet 1 → q0 q0 {q1, q2} {q1, q2} {q0, q1, q2} {q1, q2} State / Alphabet 1 → q0 q0 {q1, q2} {q1, q2} {q0, q1, q2} {q1, q2} {q0, q1, q2} {q0, q1, q2} {q1, q2} State / Alphabet 1 → q0 [q0] [q1, q2] *[q1, q2] [q0, q1, q2] [q1, q2] *[q0, q1, q2] [q0, q1, q2] [q1, q2]