将用于电子邮件验证的 NFA 转换为 DFA

Question

任何人都可以帮助解决如何将此电子邮件验证的 NFA 转换为 DFA 的问题吗？

为了进行转换，我首先创建了状态转换 table，那么有人可以帮助创建 DFA 吗？

Answer 1

从您的 epsilon 闭包生成 DFA 似乎很直接。每个闭包形成一个 DFA 状态，DFA 中的转换是 NFA epsilon 闭包中节点转换的聚合。这是来自 e-closures:

的 DFA 的转换 table

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

这是此 table (view on graphviz) 的 DFA：

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"]
}

将用于电子邮件验证的 NFA 转换为 DFA

Convert NFA for email validation into DFA

dfa

nfa