Coders Packet

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

By Abhishek Bajaj

  • E-nfa to dfa.docx
  • E-nfatodfa.cpp
  • 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



    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 will be helpful.




    Download Complete Code


    No comments yet