|
大小: 971
备注:
|
大小: 1063
备注:
|
| 删除的内容标记成这样。 | 加入的内容标记成这样。 |
| 行号 28: | 行号 28: |
| 等价： | 状态最小化算法： 推论：语言L是正则的当且仅当≈,,L,,有有穷的等价类 |
确定型有穷自动机 deterministic finite automaton: 确定型有穷自动机是一个五元组M=(K, ∑, δ, s, F)，其中 K是有穷的状态集合，∑是字母表，s∈K是初始状态，F⊆K是终结状态集合，δ是从K×∑到K的函数，叫做转移函数。
格局 configuration:
一步产生 yield in one step:
产生 yields:
接受 accept:
状态图:
非确定型有穷自动机:
定理：对于每一台非确定型有穷自动机，有一台等价的确定型有穷自动机。
定理：有穷自动机接受的语言在下属运算下是封闭的：
- 并
- 连接
- Kleene星号
- 补
- 交
定理：一个语言是正则的当且仅当它被有穷自动机接受。
泵定理： 设L是一个正则语言，则存在正整数n≥1使得任意字符串ω∈L只要|ω|≥n就可以写成ω=xyz，其中y≠e,|xy|≤n且对于每一个i≥0，xyiz∈L。
状态最小化算法：
推论：语言L是正则的当且仅当≈L有有穷的等价类