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_{0}, s_{1}, …, 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_{0}) 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:
- Construct the transition table of the given NFA machine.
- Scan the next states column in the transition table from the initial state to the final state.
- 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.
- 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.
- Repeat steps 2 to step 4 until all the states in the NFA transition table will be scanned completely.
- 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):
Present State | Next State | |
0 | 1 | |
→q_{0} | {q_{2}} | Φ |
q_{1} | Φ | {q_{0}, q_{2}} |
q_{2}* | {q_{0}, q_{1}} | {q_{0}} |
Step 2: Transition Table of DFA:
Present State | Next State | |
0 | 1 | |
→{q_{0}} | {q_{2}} | Φ |
{q_{2}} | {q_{0}, q_{1}} | {q_{0}} |
{q_{0}, q_{1}} | {q_{2}} | {q_{0}, q_{2}} |
{q_{0}, q_{2}} | {q_{0}, q_{1}, q_{2}} | {q_{0}} |
{q_{0}, q_{1}, q_{2}} | {q_{0}, q_{1}, q_{2}} | {q_{0}} |
how to convert a c language program into tokens using lex tool. Please do this practically.
thank you so much I love your work