はじめに
形式言語理論の第1回の続きです。まだ見てない人はぜひ第1回から読んでいただけると学ぶ対象が明らかになると思います！今回は有限オートマトンについて説明します。
前回は形式言語とはどういうものかについて説明をし、形式言語で記述される文字列の具体例を挙げました。これからは「形式言語を定義する文法が生成・認識する言語の範囲や特性」について詳しく学んでいきましょう。
有限オートマトンについて
では実際に形式言語を定義する文法が生成・認識する言語を考えるために、数学的なモデル、すなわち決定性有限オートマトンを導入してみます。有限オートマトンは計算モデルの一種の中でも最も単純なものです。これから有限オートマトンの定義を述べますが、形式言語との関連は後で明らかになってくるので頑張って付いてきてくださいね。
決定性有限オートマトンの定義
決定性有限オートマトンは以下の5つの要素の組 \(M = (Q, \Sigma, \delta, q_0, F)\) で定義される。
- \(Q \cdots\) 状態 (state) と呼ばれる有限集合
- \(\Sigma \cdots\) アルファベットと呼ばれる有限集合
- \(\delta\)：\(Q \times \Sigma \to Q \cdots\) 遷移関数
状態 \(p\) からアルファベットの要素 \(a\) で状態 \(q\) へ遷移するとき \(\delta(p, a) = q\) でありその遷移を表したい時は \(p\stackrel{a}{\to}q\) と書く。 - \(q_0 \in Q \cdots\) 開始状態
- \(F \subseteq Q \cdots\) 受理状態の集合
また文字列 \(w = a_1a_2 \ldots a_n\) に対して、開始状態 \(q_0\) から始まり受理状態 \(q_n \in F\) に至る遷移が存在するとき、すなわち \(q_0\stackrel{a_1}{\to}q_1\stackrel{a_2}{\to}\ldots \stackrel{a_n}{\to}q_n\) が存在するとき、決定性有限オートマトン \(M\) は文字列 \(w\) を受理するといいます。
これだけだと何のことを言っているかさっぱりだと思うので、さっそく具体例を見ていきましょう！
決定性有限オートマトンの具体例
以下の例では開始状態を \(q_1\)、アルファベットを \(\Sigma = \{0, 1\}\) とします。ある文字列を受理するような決定性有限オートマトンを作ってみます。
例1
とりあえず簡単な例で理解しようと試みましょう。例1では最後が \(1\) で終わる文字列を受理する決定性有限オートマトンを作ってみます。まだ作ったことが無い人でも、もしかしたらパズルのように考えてみれば答えを導けるかもしれないのでチャレンジしてみてください。
さて、この決定性有限オートマトンを作る手順は以下の通りです。
とりあえずどのような文字列が受理されるかを考えてみましょう。\(1\) で終わる文字列は無数に考えることができ、長さが少ないものから \(1, 01, 11, 001, 011, 101, 111, \ldots\) などが考えられます。これらの例から、\(1\) で終わる文字列を全て網羅できるような状態と遷移関数を設定すれば良いのです。
まず開始状態から遷移がない場合、すなわち空語 \((\varepsilon)\) のときは当然ですが \(1\) では終わらないので求める有限オートマトンは受理をしません。したがって、開始状態は受理状態とはなり得ないので、異なる状態へ少なくとも1度は遷移する必要があります。今回は文字列の長さを \(n\) としたとき、最初から \(n-1\) 番目までの文字が何であろうと \(n\) 番目が \(1\) であれば受理します。よって、ある状態から \(1\) で遷移する遷移先は必ず受理状態となり、ある状態から \(0\) で遷移する遷移先は必ず非受理状態となれば良いわけです。
では実際に遷移関数を求めてみます。開始状態から \(1\) で遷移する場合は受理状態になるのでこの状態を\(q_2\) とすると遷移関数は以下のようになります。
\(\delta(q_1, 1) = q_2\)
また、受理状態 \(q_2\) から \(1\) で遷移する場合も受理状態に遷移するので、
\(\delta(q_2, 1) = q_2\)
となります。次に \(0\) で遷移する場合ですが、開始状態が受理状態とならないことと、最後の文字以外は受理するかどうかに無関係であることから、非受理状態を開始状態とすれば問題ないですね。よって \(q_1, q_2\) の \(0\) での遷移に関する遷移関数は以下のようになります。
\(\delta(q_1, 0) = q_1\)
\(\delta(q_2, 0) = q_1\)
以上より全ての状態 \(Q = \{q_1, q_2\}\)と遷移関数 \(\delta\)、受理状態の集合 \(F = \{q_2\} \)を求めることができたのでオートマトン \((Q, \Sigma, \delta, q_0, F)\) が一意に定まりました。このオートマトンを表す状態遷移図は以下のようになります。ただし、非受理状態はオレンジ、受理状態は青に塗りつぶしています。
こんな感じでパズルのようにオートマトンを求めていけば良いわけです。何となく分かって来ましたか？ではあと2つほど例を見ていきましょう！
例2
次は \(1\) で始まり \(0\) で終わる文字列を受理する決定性有限オートマトンを作ってみましょう。まずはどんな文字列が受理するかをいくつか思い浮かべてみてください。先ほどの例でコツを掴んだ人は同じ要領で解けると思います。
例1と異なるのは最初の文字にも条件があることです。この場合最初の文字が \(0\) のものはそれ以降の文字が何であっても受理状態には到達することができません。とりあえずこのことを遷移関数で表してみましょう。開始状態から \(0\) で遷移する遷移先を \(q_2\) とします。すると、\(q_2\) に遷移した時点で受理状態に遷移することはあり得ません。\(q_2\) 自体も非受理状態なので、\(q_2\) からのいかなる遷移も自身に遷移するようにすれば良さそうですね。したがってここまでの話を式にすると以下のようになります。
\(\delta(q_1, 0) = q_2\)
\(\delta(q_2, 0) = q_2\)
\(\delta(q_2, 1) = q_2\)
これで \(q_1\) から \(1\) で遷移した後のことだけを考えればよいですね。ここで \(q_1\) から \(1\) で遷移したときの遷移先を \(q_3\) とします。つまり
\(\delta(q_1, 1) = q_3\)
です。ここまで来ればあとは例1をそのまま使えそうですね。\(q_3\) を例1の \(q_1\) としてみれば \(1\) と \(0\) を入れ替えるだけで全く同じ条件となります。したがって状態遷移図は以下のようになります。
例3
次は空語のみを受理する決定性有限オートマトンを作ってみましょう。
空語を受理するということは開始状態からの遷移をせずに受理することになります。したがって開始状態は受理状態になります。また空語以外は受理しないので、開始状態から遷移をしたものは全て受理しないようにします。これらを踏まえると遷移関数と状態遷移図は次のようになります。
\(\delta(q_1, 0) = q_2\)
\(\delta(q_1, 1) = q_2\)
\(\delta(q_2, 0) = q_2\)
\(\delta(q_2, 1) = q_2\)
なお、遷移関数を簡易的に表で示したいときは以下のように書くことも可能です。
有限オートマトンの応用
決定性有限オートマトンが文字列を受理する仕組みを例を通してみてきました。ここで実際のシステムに近い設定をモデル化してみましょう。
ここではアルファベット \(\Sigma = \{A, B, Enter\}\) 上でパスワード \(AB\) を入力するとロックを解除するシステムを決定性有限オートマトンでモデル化してみたいと思います。
もう少し細かい仕様を設定します。\(A, B\) を含んだ何らかの文字列を入力後に \(Enter\) を押すことにより受理状態に遷移するものとします。よって、パスワードが異なったり文字列の途中に \(Enter\) が入ってしまう場合は非受理状態に遷移します。なお、受理状態に遷移した後にいかなる文字を入力しても受理状態にとどまるようにします。
この仕様を踏まえると、考えられる状態は以下の通りです。
- 初期状態 (\(L_0\))
- \(A\) を入力している状態 (\(L_1\))
- \(AB\) を入力している状態 (\(L_2\))
- 非受理状態 (\(L_3\))
- ロックを解除している受理状態 (\(L_4\))
以上のことを考慮すれば状態遷移図を書くことができます。
おわりに
今回は形式言語を数学的にモデル化するために決定性有限オートマトンを導入し、文字列の受理がどのように行われるかを学びました。次回はこの決定性有限オートマトンと形式言語との関連について詳しく説明していきます！
