C++ program to convert a E-NFA to DFA

By Abhishek Bajaj

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.

 

The input to the program should be given like this:

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.............................................