Search code examples
dfanfa

Convert NFA for email validation into DFA

Can anyone help on how to convert the NFA for this email validation into a DFA?

Image For Email Validation NFA

In order to make the conversion I have first created state transition table, then can any one help to create DFA?

NFA State Transition Table

Solution

  • Producing a DFA from your epsilon closures seems direct. Each closure forms a single DFA state, and the transitions in the DFA are the aggregation of transitions for nodes in the epsilon closure of the NFA. Here's the transition table for the DFA from your e-closures:

       | a-z | 0-9 | @ | _  | .  | com
---|-----|-----|---|----|----|-----
A^ | AB  |     |   |    |    |
AB | AB  | AB  | C |    |    |
C  | CD  | CD  |   | CD |    |
CD | CD  | CD  |   | CD | CE |
CE | CD  | CD  |   | CD |    | F
F$ |     |     |   |    |    |

    Here's the DFA for this table (view on graphviz):

    digraph G {
    rankdir=LR;
 
    node [shape=point]; qi;
    node [shape=doublecircle]; F;
    node [shape=circle];

    qi -> A;
    A  -> AB [label="a-z"]
    AB -> AB [label="a-z | 0-9"];
    AB -> C  [label="@"]
    C  -> CD [label="a-z | 0-9 | _"]
    CD -> CD [label="a-z | 0-9 | _"]
    CD -> CE [label="."]
    CE -> CD [label="a-z | 0-9 | _"]
    CE -> F  [label="com"]
}