249
备注:
|
740
|
删除的内容标记成这样。 | 加入的内容标记成这样。 |
行号 1: | 行号 1: |
确定型有穷自动机: 确定型有穷自动机是一个五元组M=(K, ∑, δ, s, F),其中 K是有穷的状态集合,∑是字母表,s∈K是初始状态,F⊆K是终结状态集合,δ是从K×∑到K的函数,叫做转移函数。 | 确定型有穷自动机 deterministic finite automaton: 确定型有穷自动机是一个五元组M=(K, ∑, δ, s, F),其中 K是有穷的状态集合,∑是字母表,s∈K是初始状态,F⊆K是终结状态集合,δ是从K×∑到K的函数,叫做转移函数。 格局 configuration: 一步产生 yield in one step: 产生 yields: 接受 accept: 状态图: 非确定型有穷自动机: 定理:对于每一台非确定型有穷自动机,有一台等价的确定型有穷自动机。 定理:有穷自动机接受的语言在下属运算下是封闭的: a. 并 a. 连接 a. Kleene星号 a. 补 a. 交 定理:一个语言是正则的当且仅当它被有穷自动机接受。 |
确定型有穷自动机 deterministic finite automaton: 确定型有穷自动机是一个五元组M=(K, ∑, δ, s, F),其中 K是有穷的状态集合,∑是字母表,s∈K是初始状态,F⊆K是终结状态集合,δ是从K×∑到K的函数,叫做转移函数。
格局 configuration:
一步产生 yield in one step:
产生 yields:
接受 accept:
状态图:
非确定型有穷自动机:
定理:对于每一台非确定型有穷自动机,有一台等价的确定型有穷自动机。
定理:有穷自动机接受的语言在下属运算下是封闭的:
- 并
- 连接
- Kleene星号
- 补
- 交
定理:一个语言是正则的当且仅当它被有穷自动机接受。