Simple C Program For Converting Nfa To Dfa
An NFA can have zero, one or more than one move from a given state on a given input symbol. An NFA can also have NULL moves (moves without input symbol). On the other hand, DFA has one and only one move from a given state on a given input symbol.
- Simple C Code To Convert Nfa To Dfa
- Simple C Program For Converting Nfa To Dfa
- Nfa To Dfa Conversion Algorithm
Conversion from NFA to DFA
Suppose there is an NFA N < Q, ∑, q0, δ, F > which recognizes a language L. Then the DFA D < Q’, ∑, q0, δ’, F’ > can be constructed for language L as:
Step 1: Initially Q’ = ɸ.
Step 2: Add q0 to Q’.
Step 3: For each state in Q’, find the possible set of states for each input symbol using transition function of NFA. If this set of states is not in Q’, add it to Q’.
Step 4: Final state of DFA will be all states with contain F (final states of NFA)
DFA Minimization using Myphill-Nerode Theorem Algorithm. Output − Minimized DFA. Step 1 − Draw a table for all pairs of states (Q i, Q j) not necessarily connected directly All are unmarked initially. Step 2 − Consider every state pair (Q i, Q j) in the DFA where Q i ∈ F and Q j ∉ F or vice versa and mark them. Here F is the set of final states. I needed a C implementation of NFA to DFA conversion for my compilers class and could not find a simple implementation on the web so I thought I would provide one. A DFA (Deterministic Finite Automaton) is a finite state machine where from each state and a given input symbol, the next possible state is.
Example
Consider the following NFA shown in Figure 1.
Following are the various parameters for NFA.
Q = { q0, q1, q2 }
∑ = ( a, b )
F = { q2 }
δ (Transition Function of NFA)
Step 1: Q’ = ɸ
Step 2: Q’ = {q0}
Step 3: For each state in Q’, find the states for each input symbol.
Currently, state in Q’ is q0, find moves from q0 on input symbol a and b using transition function of NFA and update the transition table of DFA.
δ’ (Transition Function of DFA)
Now { q0, q1 } will be considered as a single state. As its entry is not in Q’, add it to Q’.
So Q’ = { q0, { q0, q1 } }
Now, moves from state { q0, q1 } on different input symbols are not present in transition table of DFA, we will calculate it like:
δ’ ( { q0, q1 }, a ) = δ ( q0, a ) ∪ δ ( q1, a ) = { q0, q1 }
δ’ ( { q0, q1 }, b ) = δ ( q0, b ) ∪ δ ( q1, b ) = { q0, q2 }
Now we will update the transition table of DFA.
δ’ (Transition Function of DFA)
Now { q0, q2 } will be considered as a single state. As its entry is not in Q’, add it to Q’.
So Q’ = { q0, { q0, q1 }, { q0, q2 } }
Now, moves from state {q0, q2} on different input symbols are not present in transition table of DFA, we will calculate it like:
δ’ ( { q0, q2 }, a ) = δ ( q0, a ) ∪ δ ( q2, a ) = { q0, q1 }
δ’ ( { q0, q2 }, b ) = δ ( q0, b ) ∪ δ ( q2, b ) = { q0 }
Now we will update the transition table of DFA.
δ’ (Transition Function of DFA)
As there is no new state generated, we are done with the conversion. Final state of DFA will be state which has q2 as its component i.e., { q0, q2 }
Following are the various parameters for DFA.
Q’ = { q0, { q0, q1 }, { q0, q2 } }
∑ = ( a, b )
F = { { q0, q2 } } and transition function δ’ as shown above. The final DFA for above NFA has been shown in Figure 2.
Note : Sometimes, it is not easy to convert regular expression to DFA. First you can convert regular expression to NFA and then NFA to DFA.
Question : The number of states in the minimal deterministic finite automaton corresponding to the regular expression (0 + 1)* (10) is ____________.
Solution : First, we will make an NFA for the above expression. To make an NFA for (0 + 1)*, NFA will be in same state q0 on input symbol 0 or 1. Then for concatenation, we will add two moves (q0 to q1 for 1 and q1 to q2 for 0) as shown in Figure 3.
This article has been contributed by Sonal Tuteja.
Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above
Recommended Posts:
i want to write a program that convert nfa to dfa , user draw a graph then Program convert it to dfa .how can i do it?
Moslem7026Moslem7026
Simple C Code To Convert Nfa To Dfa
2 Answers
You may want to take a look at this previous question for incites.
as indicated in the answer you could approach the problem by re-implementing the following python example in C#
If you are not bothered about the implementation language and simply wish to play with NFA's and DFA's then you can use:
here is a tutorial for doing just that:
You may also want to look at Fare.
It is a .NET port of the well established Java library dk.brics.automaton with API as close as possible to the corresponding dk.brics.automaton classes.
It even includes a .NET port of Xeger, for generating random text from regular expressions.
Nikos BaxevanisNikos Baxevanis