正则表达式 – 如何实现最大 – 蒙克？

同样值得注意的是,DFA并不完整,因为转换功能尚未完成.某些{state,input}对没有定义的结果. [笔记2]

考虑到这一点,算法如下：

Set Accepted NFA State to ⊥
Set Accepted Position to Tell(Input Stream)
Set State to Starting State
Repeat:
  If State ∈ Accepting:
    Set Accepted NFA State to Accepting NFA State for State  [Note 1]
    Set Accepted Position to Tell(Input Stream)
  Read one symbol from Input Stream into Next Symbol
  If there is a transition from {State,Next Symbol} to New State:
    Set State to New State
    Continue the loop
  Otherwise:
    Rewind Input Stream to Accepted Position
    Return Accepted NFA State

如果算法返回& bottom;,则没有识别出令牌,输入流将被重绕到初始位置.

笔记：

> NFA通常在状态和接受动作之间具有明确的同态,但是DFA构造算法可以将两个接受NFA状态与不同动作组合.在这种情况下,flex算法将优先考虑输入文件中的第一个动作.在上面的算法中,我们通过将每个接受DFA状态映射到接受具有优先级的NFA状态的组件来表示这一点.>通过添加一个不接受且只有自身转换的附加(和唯一)接收器状态,可以很容易地完成DFA.然后我们可以将接收器状态添加为任何其他未指定的转换的转换.如果我们称为沉没状态和底部;那么很清楚如何修改所提供的算法;在实践中,这根本不是必要的,因为在实践中我们并不关心DFA是不完整的.但它确实对状态最小化算法有一些影响.