"有穷自动机"版本比较

版本8和9间的区别

定义：确定型有穷自动机 deterministic finite automaton: 确定型有穷自动机是一个五元组 $M=(K, \Sigma, \delta, s, F)$ ，其中 $K$ 是有穷的状态集合， $\Sigma$ 是字母表， $s\in K$ 是初始状态， $F\subseteq K$ 是终结状态集合， $\delta$ 是从 $K\times\Sigma$ 到 $K$ 的函数，叫做转移函数。

定义：确定型有穷自动机 $(K, \Sigma, \delta, s, F)$ 的格局configuration是 $K\times\Sigma^*$ 的任一元素。

一步产生 yield in one step:如果 $(q,\omega)$ 和 $q',\omega '$ 是M的两个格局，则 $(q,\omega)\vdash_M(q',\omega ')$ 当且仅当对于某个符号 $a\in \Sigma$ ， $\omega=a\omega'$ 且 $\delta(q,a)=q'$ 。我们称它为 $(q,\omega)$ 一步产生 $(q',\omega ')$

产生 yields: $\vdash^*_M$ 表示 $\vdash_M$ 的自反传递闭包。 $(q,\omega)\vdash^*_M(q',\omega')$ 称作 $(q,\omega)$ 产生 $(q',\omega')$ 。

接受 accept:字符串 $\omega\in\Sigma^*$ 当且仅当存在状态 $q\in F$ 使 $(s,\omega)\vdash^*_M(q,e)$ 。M接受的语言是M接受的所有字符串的集合，记作 $L(M)$ 。

状态图:

非确定型有穷自动机:

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

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

并
连接
Kleene星号
补
交

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

泵定理：设L是一个正则语言，则存在正整数n≥1使得任意字符串ω∈L只要|ω|≥n就可以写成ω=xyz，其中y≠e,|xy|≤n且对于每一个i≥0，xyⁱz∈L。

状态最小化算法：

推论：语言L是正则的当且仅当≈_L有有穷的等价类

-  ⇤ ← 于2006-03-28 00:38:23修订的的版本8 → 
  大小: 1131
  编辑: czk
  备注:
+   ← 于2006-03-28 00:56:41修订的的版本9 → ⇥
  大小: 1761
  编辑: czk
  备注:
-删除的内容标记成这样。
+加入的内容标记成这样。
 行号 3:
-确定型有穷自动机 deterministic finite automaton: 确定型有穷自动机是一个五元组$M=(K, \Sigma, \delta, s, F)$，其中$K$是有穷的状态集合，$\Sigma$是字母表，$s\in K$是初始状态，$F\subseteq K$是终结状态集合，$\delta$是从$K\times\Sigma$到$K$的函数，叫做转移函数。
+定义：确定型有穷自动机 deterministic finite automaton: 确定型有穷自动机是一个五元组$M=(K, \Sigma, \delta, s, F)$，其中$K$是有穷的状态集合，$\Sigma$是字母表，$s\in K$是初始状态，$F\subseteq K$是终结状态集合，$\delta$是从$K\times\Sigma$到$K$的函数，叫做转移函数。
 行号 5:
-格局 configuration:
+定义：确定型有穷自动机$(K, \Sigma, \delta, s, F)$的格局configuration是$K\times\Sigma^*$的任一元素。
 行号 7:
-一步产生 yield in one step:
+一步产生 yield in one step:如果$(q,\omega)$和$q',\omega '$是M的两个格局，则$(q,\omega)\vdash_M(q',\omega ')$当且仅当对于某个符号$a\in \Sigma$，$\omega=a\omega'$且$\delta(q,a)=q'$。我们称它为$(q,\omega)$一步产生$(q',\omega ')$
 行号 9:
-产生 yields:
+产生 yields:$\vdash^*_M$表示$\vdash_M$的自反传递闭包。$(q,\omega)\vdash^*_M(q',\omega')$称作$(q,\omega)$产生$(q',\omega')$。
 行号 11:
-接受 accept:
+接受 accept:字符串$\omega\in\Sigma^*$当且仅当存在状态$q\in F$使$(s,\omega)\vdash^*_M(q,e)$。M接受的语言是M接受的所有字符串的集合，记作$L(M)$。