Converter NFA para validação de e-mail em DFA

Question

Alguém pode ajudar a converter o NFA para esta validação de e-mail em um DFA?

Para fazer a conversão, criei primeiro a tabela de transição de estado, então alguém pode ajudar a criar o DFA?

Answer 1

Produzir um DFA a partir de suas tampas épsilon parece direto. Cada fechamento forma um único estado DFA, e as transições no DFA são a agregação de transições para nós no fechamento épsilon do NFA. Esta é a tabela de transição para o DFA de seus fechamentos eletrônicos:

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

Este é o DFA para esta tabela ( ver no 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"]
}