Automata Conversion from NFA to DFA

The NFA to DFA conversion is based on subset construction. If a non-deterministic finite state machine consists of three states.

                Q = (q0, q1, q2,)

The machine could form a power set on Q, which in given by 2Q .

The procedure for finding whether a given string is accepted by the NFA, involves:

  • Tracing the various paths followed by the machine for the given string.
  • Finding the set of states reached from the starting state by applying the symbols of the string.
  • If the set of states obtained in step (2), contains a final state, the given string is accepted by the NFA.

The above procedure can be applied to any string by constructing a successor table.

Automata Conversion from NFA to DFA

Algorithm for contraction of successor table for the NFA of diagram is being explained, steps:

Step – 1:

Starting state {q0} is the first subset.

0 – successor of q0 is q2 δ(q0, 0 ) ⇒ q2.

1 – successor of q0 is Ф δ(q0, 0 ) ⇒ Ф.

Automata Conversion from NFA to DFA

Step – 2:

A new subset {q2} is generated. Successor of the subset {q2} are generated.

0 – successor of {q2} are {q0, q1} .

1 – successor of {q2} are {q0}.

Automata Conversion from NFA to DFA

Step – 3:

A new subset {q0, q1} is generated. Successor of the subset {q0, q1} are generated.

0 – successor of {q0, q1} = δ ({q0, q1}, 0)

                                       = δ (q0, 0) (q1, 0)

                                       = {q2} Ф

                                       = {q2}

1 – successor of {q0, q1} = δ ({q0, q1}, 1)

                                       = δ (q0, 1) (q1, 1)

                                       = Ф {q0, q2}

                                       = {q0, q2}

Automata Conversion from NFA to DFA

Step – 4:

A new subset {q0, q2} is generated successors of the subset {q0, q2} are generated.

0 – successor of {q0, q2} = δ ({q0, q2}, 0)

                                       = δ (q0, 0) (q2, 0)

                                       = {q2} {q2, q1}

                                       = {q0, q1, q2}

1 – successor of {q0, q2} = δ ({q0, q2}, 1)

                                       = δ (q0, 1) (q2, 1)

                                       = Ф {q0}

                                       = {q0}

Automata Conversion from NFA to DFA

Step – 5:

A new subset {q0, q1, q2} is generated successors of the subset {q0, q1, q2} are generated.

0 – successor of {q0, q1, q2} = δ ({q0, q1, q2}, 0)

                                             = δ ({q0, q1}, 0) (q2, 0)

                                             = {q2} {q0, q1}

                                             = {q0, q1, q2}

1 – successor of {q0, q1, q2} = δ ({q0, q1, q2}, 1)

                                             = δ ({q0, q1}, 1) (q2, 1)

                                             = {q0 ,q1 } {q0}

                                             = {q0, q2}

Automata Conversion from NFA to DFA

Step – 6:

q2 is the final state in NFA of the diagram Every subset containing q2 should be taken as a final state.

Automata Conversion from NFA to DFA

Recommended:

  1. Introduction to Finite Automata
  2. Deterministic Finite Automata (DFA)
  3. Number of 1’s is a multiple of 3 on {0,1} using DFA
  4. Number of 1’s is not multiple of 3 on {0,1} using DFA
  5. DFA for Number of 1’s is even/odd and number of 0’s is even/odd
  6. DFA for number of 0’s divisible by five and 1’s divisible by 3
  7. DFA for All string of length at most five
  8. DFA for All strings ending with abb
  9. DFA for strings in which leftmost symbol differ from rightmost
  10. Design DFA that contain word ‘CAT’ using word ‘CHARIOT’
  11. Design DFA which accept a binary number divisible by 3
  12. Non-Deterministic finite Automata
  13. Design NFA that accepts string ending with aab
  14. Design NFA to accept string containing the substring 0101
  15. Differentiate between NFA and DFA
  16. Design NFA that start with 01 and end with 10

Leave a Comment

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

x