自动机到词法分析器

• 正则表达式：识别单个模式

• 词法分析器：识别多个模式

NFA合并方法

引入新的开始状态，并引入从该开始状态到各个原开始状态的空串转换，得到的NFA所接受的语言是原来各个NFA语言的并集，不同的接受状态代表不同的模式。

确定化NFA可能引发冲突

• 对得到的NFA进行确定化，得到DFA

• 一个DFA的接受状态对应于NFA的状态子集，其中至少包括一个NFA的接受状态。如果其中包含多个对应于不同模式的NFA接受状态，则表示当前的输入前缀对应于多个模式，存在冲突。

词法分析器状态的最小化

基本思想和DFA最小化算法相同

差别：

• 词法分析器中的接受状态对应于不同的模式

• 对应不同模式的接受状态一定是不等价的

• 初始划分为：所有非接受状态集合 + 对应各个模式的接受状态集合

其余划分和构造方法均相同，接受状态对应的模式就是原来的模式