有穷自动机 - czk's wiki

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

是有穷的状态集合，
$\Sigma$ 是字母表，
$s\in K$ 是初始状态，
$F\subseteq K$ 是终结状态集合，
$\delta$ 是从 $K\times\Sigma$ 到的函数，叫做转移函数。

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

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

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

并
连接
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-2020 czk.