NFA to DFA conversion algorithm with solved example

Finite automata include two different classes Deterministic Finite Automata (DFA) and the Non deterministic Finite Automata (NFA). These are converted from one to another i.e. Non-Deterministic Finite Automata to Deterministic Finite Automata (NFA to DFA) conversion and Deterministic Finite Automata to Non-Deterministic Finite Automata (DFA to NFA) conversion. Some more enhancement of the NFA machine is NFA with ε moves i.e. (ε-NFA) can be converted into DFA and vice versa. A DFA is directly converted into a Regular expression. The below diagram explains all conversions of Finite Automata conversion.

Figure (1) : (NFA→ DFA) and (DFA→ NFA) conversion block diagram

Non Deterministic Finite Automata to Deterministic Finite Automata (NFA to DFA conversion) :

The goal is to construct a Deterministic Finite Automata (DFA) from a given Non-Deterministic Finite Automata (DFA) machine which is much faster in recognition of an input string. The main idea behind this conversion is to construct a DFA machine in which each state will correspond to a set of NFA states.

Worst Case complexity of (NFA→ DFA) conversion:

The worst-case complexity of NFA to DFA conversion is O(2^N) of sets of states. The DFA can have exponentially many more states than the NFA in rare cases.

NFA to DFA conversion Algorithm:

Input:
A NFA                         S = States = { s₀, s₁, …, s_N} = S_NFA
                                  δ = Move function = Move_NFA
                                  Move’(S, a) → Set of states

Output:
A DFA                         S = States = {?, ?, …, ?} = S_DFA
                                  δ = Move function = Move_DFA
                                  Move(s, a) → Single state from S_DFA

Main idea:
Each state in S_DFA will be a set of states from the NFA S_DFA = { {…}, {…}, …, {…} }
(The name of the states in constructed DFA is arbitrary and can be changed later if desired.)

Method:

Construct a transition table Transition_D. Each DFA state is a set of NFA states. Transition_D simulates in parallel all possible moves N can make on a given string.

Operations to keep track of sets of NFA states:

ε Closure (S):
Set of states reachable from state S via epsilon.

ε Closure (T):
Set of states reachable from any state in set T via epsilon.

move (T, a):
Set of states to which there is an NFA transition from states in T on a symbol a.

Algorithm:

initially, ε-Closure (S₀) in Transition_D.
While unmarked state T in Transition_D
    mark T
for each input symbol ‘a’
do u = ε Closure (T, a)
If u is not in Transition_D
then add u to Transition_D
Transition [T, a] = U

The following algorithm shows a computation of ε -Closure function.
Push all states in T onto the stack.
initialize ε-Closure (T) to T
while the stack is not empty
do pop top element t
for each state u with ε-edge
t to u
do If u is not in ε-Closure(T)
do add u ε Closure (T)
push u onto the stack

Remarkable Steps to convert NFA→ DFA:

1. Construct the transition table of the given NFA machine.
2. Scan the next states column in the transition table from the initial state to the final state.
3. If any of the next states consists of more than one state on the single input alphabet. Then merge them and make it a new state. Place this newly constructed state in the DFA transition table as the present state.
4. The next state of this newly constructed state on the input alphabet will be the summation of each next state which parts in the NFA transition table.
5. Repeat steps 2 to step 4 until all the states in the NFA transition table will be scanned completely.
6. The final transition table must have a single next state at a single input alphabet.

Example:

Figure (1): NFA

Construct the equivalent DFA of the NFA given in figure (1).
Step 1: Transition Table of NFA from Figure (1):

Step 2: Transition Table of DFA: