Search code examples
automatadfanfa

NFA to DFA conversion confusion?


I have this NFA in the book given:

Example NFA

And their solved DFA result was this:

Resultant NFA

But According to my solved solution (by finding e-closure of each state), it looks something like this:

    |  a   |  b  | c
----+----- +-----+---
ABD | CEBD |  Φ  | C
BD  | EBD  |  Φ  | C
C   |  Φ   | EBD | Φ
D   | EBD  |  Φ  | Φ
EBD | EBD  |  Φ  | C
CEBD| EBD  | EBD | C

What am I missing?


Solution

  • Your solution is identical to the DFA diagram, with two differences:

    • Your table contains unreachable states (BD, D). Those are culled from the diagram.
    • There is a misprint in the diagram. The two arrows between {C} and {BDE} have their labels switched. (The arrow going from {C} to {BDE} should be labeled b, and the arrow from {BDE} to {C} should be labeled c.)