I have written a c++ program that converts an Epsilon-Nondeterministic finite automaton(e-NFA) to a deterministic finite automaton(DFA).
The program is pretty straightforward. It follows the general rules and ways to convert an e-NFA to DFA which are:
1)find the epsilon of each state.
2)epsilon of the starting state of e-NFA is considered as the starting state for DFA.------(consider it to be X)
3)Find all the states reached by each of the individual states present in the starting state of DFA.-------(if X is ABC then find states from A on 0 and Same for B and C)
4)Find their epsilons and union them.------------(if A on 0 gives B, C then (B's epsilon UNION C's epsilon) UNION if B on 0 gives B then (B's epsilon) UNION if C on 0 gives -- then (NONE)).
5)repeat the above steps till there is no new state available.
For more visually understanding it go to youtube and type e-NFA to DFA and you will get millions of videos.
noofstates noofgivensymbols
all the states of the e-NFA table
e-NFA transition table
eg:
3 3
A B C
B C 0
A 0 0
B 0 0
0 0 0
B 0 0
C 0 0
C 0 0
C 0 0
0 0 0
In this '0' means no states are reached.
First, understand the process completely then try understanding the code.
I have included a word file with some examples too.it will be helpful.
PEACE.............................................
Submitted by Abhishek Bajaj (ABBHISHEK)
Download packets of source code on Coders Packet
Comments