首页 > 代码库 > 词法分析备忘

词法分析备忘

构造最小DFA:

  1. 构造NFA(课本上的构造法是不带ε边的,少了消ε的过程)
  2. NFA->DFA
  3. 最小化DFA

构造NFA:

连接、并、重复

NFA->DFA:

从初始状态集合{S}开始,跑所有字符集,若得到新的状态集则入队。

带有终结状态的集合仍然是终结状态。

对状态重新编号。

DFA的最小化:

  1. 构造一个初始划分Π:终态集合,非终态集合。
  2. 对Π重新划分,直到不能划分出新的Π。

划分:

对于Π中每一个组G,若G中的两个状态对所有符号两个状态转换后的状态都处于Π的同一个组中,则这两个状态划分后仍在同一个组。否则在两个不同的组。

重新编号组。含有初始状态的仍是初始状态,含有终结状态的仍是终结状态。

词法分析备忘