版本2和3间的区别
于2006-02-18 21:56:41修订的的版本2
大小: 249
编辑: czk
备注:
于2006-02-18 22:11:30修订的的版本3
大小: 740
编辑: czk
备注:
删除的内容标记成这样。 加入的内容标记成这样。
行号 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:

状态图:

非确定型有穷自动机:

定理:对于每一台非确定型有穷自动机,有一台等价的确定型有穷自动机。

定理:有穷自动机接受的语言在下属运算下是封闭的:

  1. 连接
  2. Kleene星号

定理:一个语言是正则的当且仅当它被有穷自动机接受。

有穷自动机 (2021-03-18 12:05:14由czk编辑)

ch3n2k.com | Copyright (c) 2004-2020 czk.