Search code examples
algorithmfinite-automatadfanfa

A succinct description of NFA to DFA conversion?

Can someone much brighter than I succinctly describe to the SO community the NFA to DFA conversion algorithm? (Preferably in 500 words or less.) I've seen diagrams and lectures that have only served to confuse what I thought I once knew. I'm mostly confident in generating an initial NFA transition table from a state diagram, but after that, I lose the DFA in the epsilons and subsets.

1) In a transition (delta) table, which column represents the new DFA states? Is it the first column of generated states?

2) In row {2,3}, col 0 of my example below, what does the {2,3} mean about the NFA in terms of its state diagram? (Sorry, I must think in pictures.) And I assume it will be a "loop-back on input 0" in the DFA?

3) Any simple "rules of thumb" on getting from the table to the DFA or on recognizing the accept states of the resulting DFA?

Finitely Autonomous

delta  |  0    |  1     |
=======+=======+========+
{1}    |{1}    |{2}     |
{2}    |{3}    |{2,3}   |
{3}    |{2}    |{2,4}   |
{2,3}  |{2,3}  |{2,3,4} |
{2,4}  |{3,4}  |{2,3,4} |
{2,3,4}|{2,3,4}|{2,3,4} |
{3,4}  |{2,4}  |{2,4}   |

Edit: Here is the above table in dot format, cheers Regexident.

digraph dfa {
    rankdir = LR;
    size = "8,5"
/*  node [shape = doublecircle]; "1";*/
    node [shape = circle];

    "1" -> "1" [ label = "0" ];
    "1" -> "2" [ label = "1" ];

    "2" -> "3"   [ label = "0" ];
    "2" -> "2_3" [ label = "1" ];

    "3" -> "2"   [ label = "0" ];
    "3" -> "2_4" [ label = "1" ];

    "2_3" -> "2_3"   [ label = "0" ];
    "2_3" -> "2_3_4" [ label = "1" ];

    "2_4" -> "2_3"   [ label = "0" ];
    "2_4" -> "2_3_4" [ label = "1" ];

    "2_3_4" -> "2_3_4" [ label = "0" ];
    "2_3_4" -> "2_3_4" [ label = "1" ];
    "3_4" -> "2_4" [ label = "0" ];
    "3_4" -> "2_4" [ label = "1" ];
}

And here in rendered form:

Rendered dot graph

Note: The table lacks any information regarding state acceptance, hence so does the graph.

Solution

  • When you construct a DFA from an NFA you basically find those sets of states that the NFA can be in a time (like simulating the NFA). First you begin with the start state and then find all states that can be reached through epsilon transitions. This set of states form the start state of the resulting DFA. Then you follow the outgoing transitions from this state set. Those may lead to another NFA state, for that you find the states reachable through epsilon inputs again, and you will get another set of NFA states that will be a new DFA state. You do this process until you have finished.

    The point is, that the resulting DFA states will become sets of the old NFA states, that are compatible (regarding to epsilon transitions). These sets may also overlap, that is no error. And now I can answer your questions:

    1) The first column represents the new DFA states. It shows the NFA state sets that form the given DFA state.

    2) Your assumption is correct, it means loopback to state {2,3} on 0 input.

    3) The DFA table can be easily constructed from this table, just name your states with letters. Any DFA states that contain at least one NFA accept state will become accept states in the DFA, too.

    I hope I was clear enough.