|
大小: 2107
备注:
|
大小: 0
备注:
|
| 删除的内容标记成这样。 | 加入的内容标记成这样。 |
| 行号 1: | 行号 1: |
| #format inline_latex 定义：'''确定型有穷自动机''' 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$ 两台有穷自动机M1和M2是等价的当且仅当L(M1)=L(M2)。 定理：对于每一台非确定型有穷自动机，有一台等价的确定型有穷自动机。 定理：有穷自动机接受的语言在下属运算下是封闭的： a. 并 a. 连接 a. Kleene星号 a. 补 a. 交 定理：一个语言是正则的当且仅当它被有穷自动机接受。 泵定理： 设L是一个正则语言，则存在正整数n≥1使得任意字符串ω∈L只要|ω|≥n就可以写成ω=xyz，其中y≠e,|xy|≤n且对于每一个i≥0，xy^i^z∈L。 状态最小化算法： 推论：语言L是正则的当且仅当≈,,L,,有有穷的等价类 |