形式语言与逻辑/有限状态自动机

定义（确定性有限状态自动机）:

一个**确定性有限状态自动机**（简称 DFA）是一个五元组 $A=(Q,\Sigma ,\delta ,q_{0},F)$，其中 $Q=\{q_{1},\ldots ,q_{n}\}$ 是一个有限集，$\Sigma$ 是一个有限字母表，$\delta :Q\times \Sigma \to Q$ 是一个函数，$q_{0}\in Q$，以及 $F\subseteq Q$.

定义（状态）:

令 $A=(Q,\Sigma ,\delta ,q_{0},F)$ 为一个确定性有限状态自动机。那么 $A$ 的一个**状态** 是 $Q$ 的一个元素。

定义（初始状态）:

令 $A=(Q,\Sigma ,\delta ,q_{0},F)$ 为一个确定性有限状态自动机。那么 $A$ 的**初始状态** 是 $q_{0}$.

定义（转移函数）:

令 $A=(Q,\Sigma ,\delta ,q_{0},F)$ 为一个确定性有限状态自动机。那么 $\delta$ 是**转移函数**。

定义（接受状态）:

令 $A=(Q,\Sigma ,\delta ,q_{0},F)$ 为一个确定性有限状态自动机。那么**接受状态** 是 $F$ 的一个元素。

命题（每个接受状态都是一个状态）:

令 $A=(Q,\Sigma ,\delta ,q_{0},F)$ 为一个确定性有限状态自动机。那么 $A$ 的每个接受状态都是一个状态。

证明：这是因为 $F\subseteq Q$。 $\Box$

定义（广义转移函数）:

令 $A=(Q,\Sigma ,\delta ,q_{0},F)$ 为一个确定性有限状态自动机。那么广义转移函数 $\delta ^{*}:Q\times \Sigma ^{*}\to Q$ 是定义在 $\Sigma *$ 上的函数，它根据单词长度进行归纳定义如下

1. 对于一个单字 $a\in \Sigma$，$\delta ^{*}(q,a):=\delta ((q,a))$
2. 只要 $w=a_{1}a_{2}\cdots a_{n}\in \Sigma ^{*}$，那么 $\delta ^{*}(q,w):=\delta (\delta ^{*}(q,a_{1}a_{2}\cdots a_{n-1}),a_{n})$

定义（确定性有限状态自动机接受的语言）:

令 $A=(Q,\Sigma ,\delta ,q_{0},F)$ 为一个有限状态自动机。确定性有限状态自动机 $A$ 接受的语言定义为

$L(A):=\{w\in \Sigma ^{*}|\delta ^{*}(q_{0},w)\in F\}$.

定理（有限状态自动机精确地接受正则语言）:

当 $A=(Q,\Sigma ,\delta ,q_{0},F)$ 是一个有限状态自动机时，由 $A$ 接受的语言是正则语言。当 $L$ 是一个正则语言时，存在一个有限状态自动机接受它。

证明：首先令 $A=(\Sigma ,Q,\delta ,q_{0},F)$ 为一个有限状态自动机。定义一个乔姆斯基文法 $G=(\Sigma ,N,P,S)$ 如下：$N=Q$，$S=q_{0}$，且产生式如下所示：

${\displaystyle }$ $\Box$