版本6和16间的区别 (跳过第10版)
⇤ ← 于2006-02-18 23:22:11修订的的版本6 →
大小: 1063
编辑: czk
备注:
← 于2021-03-18 12:05:14修订的的版本16 → ⇥
大小: 2155
编辑: czk
备注:
删除的内容标记成这样。 加入的内容标记成这样。
行号 1: 行号 1:
确定型有穷自动机 deterministic finite automaton: 确定型有穷自动机是一个五元组M=(K, ∑, δ, s, F)，其中 K是有穷的状态集合，∑是字母表，s∈K是初始状态，F⊆K是终结状态集合，δ是从K×∑到K的函数，叫做转移函数。 #format inline_latex
行号 3: 行号 3:
格局 configuration: 定义：'''确定型有穷自动机''' deterministic finite automaton: 确定型有穷自动机是一个五元组$M=(K, \Sigma, \delta, s, F)$，其中
 * $K$是有穷的状态集合，
 * $\Sigma$是字母表，
 * $s\in K$是初始状态，
 * $F\subseteq K$是终结状态集合，
 * $\delta$是从$K\times\Sigma$到$K$的函数，叫做转移函数。
行号 5: 行号 10:
一步产生 yield in one step: 定义：确定型有穷自动机$(K, \Sigma, \delta, s, F)$的格局configuration是$K\times\Sigma^*$的任一元素。
行号 7: 行号 12:
产生 yields: 一步产生 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: 行号 14:
接受 accept: 产生 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)$。
行号 13: 行号 20:
非确定型有穷自动机: 非确定型有穷自动机是一个五元组：$M=(K,\Sigma,\Delta,s,F)$，其中
 * K是有穷的状态集合
 * $\Sigma$是字母表
 * $s\in K$是初始状态
 * $F\subseteq K$是终结状态集合
 * $\Delta\subseteq K \times (\Sigma\cup\lbrace e\rbrace)\times K$

两台（确定或者非确定的）有穷自动机$M_1$和$M_2$是等价的当且仅当$L(M_1)=L(M_2)$。
行号 26: 行号 40:
泵定理： 设L是一个正则语言，则存在正整数n≥1使得任意字符串ω∈L只要|ω|≥n就可以写成ω=xyz，其中y≠e,|xy|≤n且对于每一个i≥0，xy^i^z∈L。 泵定理： 设L是一个正则语言，则存在正整数$n\ge 1$使得任意字符串$\omega\in L$只要$|\omega|\ge n$就可以写成$\omega=xyz$，其中$y\ne e$,$|xy|\le n$且对于每一个$i\ge 0$，$xy^iz\in L$。

定义：确定型有穷自动机 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)$。

状态图:

非确定型有穷自动机是一个五元组：$M=(K,\Sigma,\Delta,s,F)$，其中

  • K是有穷的状态集合

  • $\Sigma$是字母表

  • $s\in K$是初始状态

  • $F\subseteq K$是终结状态集合

  • $\Delta\subseteq K \times (\Sigma\cup\lbrace e\rbrace)\times K$

两台（确定或者非确定的）有穷自动机$M_1$和$M_2$是等价的当且仅当$L(M_1)=L(M_2)$。

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

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

  1. 并
  2. 连接
  3. Kleene星号
  4. 补
  5. 交

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

泵定理： 设L是一个正则语言，则存在正整数$n\ge 1$使得任意字符串$\omega\in L$只要$|\omega|\ge n$就可以写成$\omega=xyz$，其中$y\ne e$,$|xy|\le n$且对于每一个$i\ge 0$，$xy^iz\in L$。

状态最小化算法：

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

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

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