形式語言與邏輯/有限狀態自動機

定義（確定性有限狀態自動機）:

一個**確定性有限狀態自動機**（簡稱 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$