定义:确定型有穷自动机 deterministic finite automaton: 确定型有穷自动机是一个五元组$M=(K, \Sigma, \delta, s, F)$,其中

定义:确定型有穷自动机$(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)$,其中

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

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

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

  1. 连接
  2. Kleene星号

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

泵定理: 设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有有穷的等价类

有穷自动机 (last edited 2021-03-18 12:05:14 by czk)

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