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

     

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

    Download Complete Code

    Comments

    No comments yet