はじめに
形式言語理論の第1回の続きです。まだ見てない人はぜひ第1回から読んでいただけると学ぶ対象が明らかになると思います!今回は有限オートマトンについて説明します。
前回は形式言語とはどういうものかについて説明をし、形式言語で記述される文字列の具体例を挙げました。これからは「形式言語を定義する文法が生成・認識する言語の範囲や特性」について詳しく学んでいきましょう。
有限オートマトンについて
では実際に形式言語を定義する文法が生成・認識する言語を考えるために、数学的なモデル、すなわち決定性有限オートマトンを導入してみます。有限オートマトンは計算モデルの一種の中でも最も単純なものです。これから有限オートマトンの定義を述べますが、形式言語との関連は後で明らかになってくるので頑張って付いてきてくださいね。
決定性有限オートマトンの定義
決定性有限オートマトンは以下の5つの要素の組
状態 (state) と呼ばれる有限集合 アルファベットと呼ばれる有限集合 : 遷移関数
状態 からアルファベットの要素 で状態 へ遷移するとき でありその遷移を表したい時は と書く。 開始状態 受理状態の集合
また文字列
これだけだと何のことを言っているかさっぱりだと思うので、さっそく具体例を見ていきましょう!
決定性有限オートマトンの具体例
以下の例では開始状態を
例1
とりあえず簡単な例で理解しようと試みましょう。例1では最後が
さて、この決定性有限オートマトンを作る手順は以下の通りです。
とりあえずどのような文字列が受理されるかを考えてみましょう。
まず開始状態から遷移がない場合、すなわち空語
では実際に遷移関数を求めてみます。開始状態から
また、受理状態
となります。次に
以上より全ての状態
こんな感じでパズルのようにオートマトンを求めていけば良いわけです。何となく分かって来ましたか?ではあと2つほど例を見ていきましょう!
例2
次は
例1と異なるのは最初の文字にも条件があることです。この場合最初の文字が
これで
です。ここまで来ればあとは例1をそのまま使えそうですね。
例3
次は空語のみを受理する決定性有限オートマトンを作ってみましょう。
空語を受理するということは開始状態からの遷移をせずに受理することになります。したがって開始状態は受理状態になります。また空語以外は受理しないので、開始状態から遷移をしたものは全て受理しないようにします。これらを踏まえると遷移関数と状態遷移図は次のようになります。
なお、遷移関数を簡易的に表で示したいときは以下のように書くことも可能です。
有限オートマトンの応用
決定性有限オートマトンが文字列を受理する仕組みを例を通してみてきました。ここで実際のシステムに近い設定をモデル化してみましょう。
ここではアルファベット
もう少し細かい仕様を設定します。
この仕様を踏まえると、考えられる状態は以下の通りです。
- 初期状態 (
) を入力している状態 ( ) を入力している状態 ( )- 非受理状態 (
) - ロックを解除している受理状態 (
)
以上のことを考慮すれば状態遷移図を書くことができます。
おわりに
今回は形式言語を数学的にモデル化するために決定性有限オートマトンを導入し、文字列の受理がどのように行われるかを学びました。次回はこの決定性有限オートマトンと形式言語との関連について詳しく説明していきます!