有穷自动机:修订间差异

来自吾萌百科
标签已被回退
第30行: 第30行:


<math>
<math>
\begin{align}
\begin{alignat}
Q=\{q_0,q_1\}\\
Q=\{q_0,q_1\}\\
\Sigma=\{0,1\}\\
\Sigma=\{0,1\}\\
第40行: 第40行:
\end{Bmatrix}\\
\end{Bmatrix}\\
F=\{q_1\}
F=\{q_1\}
\end{align}
\end{alignat}
</math>
</math>


假如对于上面的确定性有穷自动机<math>\mathcal M_1</math>,输入字符串<math>010</math>,此时从初始状态<math>q_0</math>开始,读入第一个字符<math>0</math>,因为<math>\delta(q_0,0)=q_1</math>,所以转移状态至<math>q_1</math>,继续读入下一个字符<math>1</math>,因为<math>\delta(q_1,1)=q_0</math>,所以转移状态至$q_0$,继续读入下一个字符<math>0</math>,因为<math>\delta(q_0,0)=1</math>所以转移状态至<math>q_1</math>,运算结束。因为最后停在状态<math>q_1</math>,因为<math>q_1 \in F</math>,所以确定性有穷自动机<math>\mathcal M_1</math>接受字符串<math>010</math>。
假如对于上面的确定性有穷自动机<math>\mathcal M_1</math>,输入字符串<math>010</math>,此时从初始状态<math>q_0</math>开始,读入第一个字符<math>0</math>,因为<math>\delta(q_0,0)=q_1</math>,所以转移状态至<math>q_1</math>,继续读入下一个字符<math>1</math>,因为<math>\delta(q_1,1)=q_0</math>,所以转移状态至$q_0$,继续读入下一个字符<math>0</math>,因为<math>\delta(q_0,0)=1</math>所以转移状态至<math>q_1</math>,运算结束。因为最后停在状态<math>q_1</math>,因为<math>q_1 \in F</math>,所以确定性有穷自动机<math>\mathcal M_1</math>接受字符串<math>010</math>。

2022年2月19日 (六) 16:58的版本

确定性有穷自动机 (Deterministic Finite Automaton, DFA)

定义

确定性有穷自动机是一个5元组[math]\displaystyle{ (Q,\Sigma,\delta,q_0,F) }[/math],其中

  1. Q是一个有穷集合,称为状态集
  2. [math]\displaystyle{ \Sigma }[/math]是一个有穷集合,称为字母表
  3. [math]\displaystyle{ \delta:Q×\Sigma \rightarrow Q }[/math]是状态转移函数
  4. [math]\displaystyle{ q_0\in Q }[/math]是起始状态
  5. [math]\displaystyle{ F\subseteq Q }[/math]是接受状态集

一台确定性有穷自动机有如上五个部分组成,介绍如下:

  1. 它有一个状态集,表示它有的全部状态
  2. 它有一个输入字母表,指明所有允许的输入符号
  3. 它有一个根据一个输入字符从一个状态到另一个状态的规则
  4. 它有一个起始状态,表示处理所起始的状态
  5. 它有一个接受状态集,表示处理表达为接受的状态

用处

主要对于输入的字符串判定是否该确定性有穷自动机所识别的语言,对此表示接受及不接受。

而如上的确定性有穷自动机是识别以0结尾的串,对于以0结尾的串[math]\displaystyle{ x \in \Sigma^* }[/math],表示接受,反之不接受。

确定性有穷自动机可以用来定义语言也可用于识别语言。

运算

假如现在有个确定性有穷自动机[math]\displaystyle{ \mathcal M_1=(Q,\Sigma,\delta,q_0,F) }[/math]

[math]\displaystyle{ \begin{alignat} Q=\{q_0,q_1\}\\ \Sigma=\{0,1\}\\ \delta=\begin{Bmatrix} \delta(q_0,0)=q_1\\ \delta(q_0,1)=q_0\\ \delta(q_1,0)=q_1\\ \delta(q_1,1)=q_0 \end{Bmatrix}\\ F=\{q_1\} \end{alignat} }[/math]

假如对于上面的确定性有穷自动机[math]\displaystyle{ \mathcal M_1 }[/math],输入字符串[math]\displaystyle{ 010 }[/math],此时从初始状态[math]\displaystyle{ q_0 }[/math]开始,读入第一个字符[math]\displaystyle{ 0 }[/math],因为[math]\displaystyle{ \delta(q_0,0)=q_1 }[/math],所以转移状态至[math]\displaystyle{ q_1 }[/math],继续读入下一个字符[math]\displaystyle{ 1 }[/math],因为[math]\displaystyle{ \delta(q_1,1)=q_0 }[/math],所以转移状态至$q_0$,继续读入下一个字符[math]\displaystyle{ 0 }[/math],因为[math]\displaystyle{ \delta(q_0,0)=1 }[/math]所以转移状态至[math]\displaystyle{ q_1 }[/math],运算结束。因为最后停在状态[math]\displaystyle{ q_1 }[/math],因为[math]\displaystyle{ q_1 \in F }[/math],所以确定性有穷自动机[math]\displaystyle{ \mathcal M_1 }[/math]接受字符串[math]\displaystyle{ 010 }[/math]