計算理論学習ノート - 有限オートマトン

---

この記事は「計算理論の基礎(共立出版)」の読書ノートです

---

有限オートマトンはメモリ容量が著しく制限された計算機に対する良いモデルとなる。

有限オートマトンは次の5つの組からなる数学的対象だ。

• 有限集合$${Q}$$: 状態集合と呼ばれ、要素を状態という

• 有限集合$${\Sigma}$$: アルファベットとよばれ、要素を文字という

• 関数$${\delta: Q \times \Sigma \to Q}$$: 遷移関数という

• 状態$${q_0 \in Q}$$: 開始(初期)状態という

• 集合$${F \sub Q}$$: 受理状態集合といい、要素を受理(最終)状態という

有限オートマトン$${M}$$が文字列$${(x_i)_{i=1}^n}$$を受け取り、遷移後の状態$${\delta(\cdots\delta(\delta(q_0, x_1), x_2)\cdots, x_n)}$$が受理状態であるとき、有限オートマトン$${M}$$は文字列$${(x_i)}$$を受理するという。

$${A}$$を有限オートマトン$${M}$$が受理するすべての文字列の集合としよう。このとき$${A}$$は機械$${M}$$の言語といい、$${L(M)}$$とかく。またこのことを$${M}$$は$${A}$$を認識するという。

有限オートマトンは複数の文字列を受理できるが、認識できる言語は唯一であるため、$${L(M)}$$という関数としての表記はよく定義されている。なお、有限オートマトンが任意の文字列を受理できないとき、そのような有限オートマトンが認識する言語は空集合$${\phi}$$となる。言語として空集合を扱う場合特に空言語と呼ぶことにする。

有限オートマトンの簡単な例を二つ上げよう。

まず一つ目は次のような$${M_1 \equiv (Q, \Sigma, \delta, q_1, \{q_2\})}$$だ。

• $${Q \equiv \{q_1, q_2\}}$$

• $${\Sigma \equiv \{0,1\}}$$

• $${\delta}$$の定義は以下の通り

$$
\begin{array}{c|cc}
& 0 & 1 \\
\hline q_1 & q_1 & q_2 \\
q_2 & q_1 & q_2
\end{array}
$$

この有限オートマトンは$${q_2}$$が受理状態であり、遷移関数$${\delta}$$の定義を見ると、$${1}$$が与えられたときのみ受理状態に達することから、$${L(M_1) \equiv \{w: wは1で終わる\}}$$となる。

二つ目は$${M_2 \equiv (Q, \Sigma, \delta, q_1, \{q_1\})}$$だ。$${Q, \Sigma, \delta}$$は$${M_1}$$と同じものを用いるとする。違いは受理状態が$${q_1}$$であることだ。$${0}$$が与えられたときのみ受理状態に達することから、$${0}$$で終わる文字列は受理される。ただし、何も入力が与えられない、つまり空文字列$${\varepsilon}$$出会った場合も受理状態に達するため、$${L(M_2) \equiv \{w: wは\varepsilon か0で終わる\}}$$となる。