ある文字列が言語の要素かどうかが一意に定まることが形式言語の重要な特徴だと述べました。オートマトンは文字列が言語の要素かどうかを判定する概念上の「機械」です。オートマトンは、文字列を受け取ると、「はい」か「いいえ」のどちらかを返します。「はい」がかえってきたら入力した文字列は言語の要素だということです。どのような機械かは後回しにして、ここではオートマトンがどのように使われるかを見ます。
オートマトンは大きく分けて二種類の使い方があります。最もベーシックなものは、使いたい形式言語が先に頭にあって、その形式言語を判定するオートマトンを作る場合です。例えば、「コンピュータ」という文字列を含む文書を取ってきたい場合を考えます。文字列に「コンピュータ」が含まれるときかつそのときのみ「はい」と答えるオートマトンが作れたら、文書を一つずつこのオートマトンに入力して、「はい」と答えが返ってきた文書だけを表示すれば文書検索が完了します。
二番目の使い方は、使い方というより考え方といった方がよいかもしれません。まず、何かオートマトンを先に作ってしまいます。そして、このオートマトンが「はい」と答える文字列の集合でもって形式言語を定義します。このオートマトンは、この定義した言語の要素を受け取ったときかつそのときのみ「はい」と答えます（そのように言語を定義したので当たり前ですね。）これにより、「コンピュータを含む文字列全体」のように、言葉で定義できる形式言語の枠を超えて、数学的に形式言語を定義できるようになります。
この二つの例が示すように、形式言語とオートマトンは表裏一体です。形式言語があればそれに対応するオートマトンができるし、逆にオートマトンがあればそれに対応する言語ができます。形式言語を学ぶにはオートマトンへの深い理解が不可欠です。
オートマトンにはいくつかの種類があります。代表的なものには、決定性有限オートマトン、プッシュダウンオートマトン、線形拘束オートマトンなどがあります。それぞれ使える機能が異なり、機能が少ないオートマトンでは表現できない言語があったりします。それぞれのオートマトンに何ができて何ができないかを知ることが形式言語理論の大きな目標です。
この講義では、最も代表的な決定性有限オートマトンと非決定性有限オートマトンについて学びます。
- 文字列が言語の要素かどうかを判定する概念上の機械をオートマトンという
- オートマトンは言語を定義することにも使える
- オートマトンには使える機能によっていくつかの種類に分かれる
次回から有限オートマトンについて学んでいきます。
