# Ch2 词法分析

把 input 分解成一个个 token

# Regular Expression

• Language: a set of strings
• String: a finite sequence of characters

Regular Experssion Notations:

# RE 转 NFA

# NFA 转 DFA

从初始状态的闭包开始，每次根据 \epsilon 和当前状态的闭包，得到下一个状态的闭包，直到得到终态的闭包。

example

🌰
把这个 NFA 转成等价的 DFA

初态的闭包是 1、2、6，1、2、6 经过 a 可以转移到 3、7，因为有 \epsilon 转移，所以 3、7 的闭包是 3、4、7、8，同理 3、4、7、8 经过 b 可以到 5、8，由于 8 是终态，把所有包含 8 的圆圈画成终态的环。

# 最小化 DFA

含义：

1. 没有多余状态：

• 从这个状态没有通路到达终态
• 从开始状态出发，任何输入串也不能到达的那个状态

2. 没有两个状态相互等价