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 = (q₀, q₁, q₂,)

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

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.

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

Step – 1:

Starting state {q₀} is the first subset.

0 – successor of q₀ is q₂ δ(q₀, 0 ) ⇒ q₂.

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

Step – 2:

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

0 – successor of {q₂} are {q₀, q₁} .

1 – successor of {q₂} are {q₀}.

Step – 3:

A new subset {q₀, q₁} is generated. Successor of the subset {q₀, q₁} are generated.

0 – successor of {q₀, q₁} = δ ({q₀, q₁}, 0)

                                       = δ (q₀, 0) ∪ (q₁, 0)

                                       = {q₂}∪ Ф

                                       = {q₂}

1 – successor of {q₀, q₁} = δ ({q₀, q₁}, 1)

                                       = δ (q₀, 1) ∪ (q₁, 1)

                                       = Ф ∪ {q₀, q₂}

                                       = {q₀, q₂}

Step – 4:

A new subset {q₀, q₂} is generated successors of the subset {q₀, q₂} are generated.

0 – successor of {q₀, q₂} = δ ({q₀, q₂}, 0)

                                       = δ (q₀, 0) ∪ (q₂, 0)

                                       = {q₂} ∪ {q₂, q₁}

                                       = {q₀, q₁, q₂}

1 – successor of {q₀, q₂} = δ ({q₀, q₂}, 1)

                                       = δ (q₀, 1) ∪ (q₂, 1)

                                       = Ф ∪ {q₀}

                                       = {q₀}

Step – 5:

A new subset {q₀, q₁, q₂} is generated successors of the subset {q₀, q₁, q₂} are generated.

0 – successor of {q₀, q₁, q₂} = δ ({q₀, q₁, q₂}, 0)

                                             = δ ({q₀, q₁}, 0) ∪ (q₂, 0)

                                             = {q₂} ∪ {q₀, q₁}

                                             = {q₀, q₁, q₂}

1 – successor of {q₀, q₁, q₂} = δ ({q₀, q₁, q₂}, 1)

                                             = δ ({q₀, q₁}, 1) ∪ (q₂, 1)

                                             = {q₀ ,q₁ } ∪ {q₀}

                                             = {q₀, q₂}

Step – 6:

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

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