有限オートマトンと正規言語

有限オートマトンは最も単純な計算機械であり、限られた数の内部状態のみを用いて一度に1つの記号を読み込みます。そして、それらが認識する言語はまさに正規言語です。

Definition

有限オートマトンは、有限の状態集合、入力記号に対する遷移関数、開始状態、および受理状態を持つ機械です。文字列を読み込んだときに、開始状態から受理状態に到達すればその文字列を受理し、受理された文字列の集合がその言語となります。

Scope

このトピックでは、決定性および非決定性有限オートマトン、部分集合構成によるそれらの等価性、正規表現とクリーネの定理、Myhill–Nerodeの定理と状態最小化、正規言語の閉包特性、および特定の言語が正規ではないことを証明するために使用されるポンピング補題について扱います。

Core questions

• 固定された有限量のメモリのみを使用して認識できる言語は何ですか？
• 決定性有限オートマトンと非決定性有限オートマトンが同等の能力を持つのはなぜですか？
• 特定の言語が正規ではないことをどのように証明できますか？
• 与えられた正規言語を認識する最小のオートマトンは何ですか？

Key theories

部分集合構成

任意の非決定性有限オートマトンは、元の状態の集合を状態とする決定性オートマトンによってシミュレートでき、これにより両モデルが全く同じ言語を認識することが証明されます。

クリーネの定理

ある言語が有限オートマトンによって認識されるのは、それが正規表現によって記述される場合にかぎり、正規言語の機械的記述と代数的記述の等価性を確立します。

Myhill–Nerodeの定理

ある言語が正規であるのは、その文字列の不可分性関係が有限個のクラスを持つ場合に限られ、これらのクラスがその言語に対する一意な最小決定性オートマトンを決定します。

Clinical relevance

有限オートマトンは、正規表現マッチング、コンパイラのスキャナおよび字句解析器、テキストエディタの検索・置換、ネットワーク侵入システムにおけるパターン検出の基盤となっており、限られたメモリでの認識により処理が高速かつ予測可能になります。

History

McCullochとPittsによる1943年の神経網モデルに基づき、クリーネは1951年頃に有限オートマトンが表現できる事象を特徴付けました。RabinとScottは1959年に非決定性オートマトンとその決定問題を形式化し、この業績は後にチューリング賞を受賞しました。

Key figures

• Stephen Kleene
• Michael Rabin
• Dana Scott
• Anil Nerode

Seminal works

• rabinScott1959
• sipser2013

Frequently asked questions

言語が正規ではないことをどのように示しますか？

最も一般的なツールはポンピング補題です。これは、正規言語内の十分に長いすべての文字列には、言語内に留まりながら任意の回数繰り返すことができる部分文字列が含まれると述べています。このようにポンピングできない文字列を見つけることで、その言語が正規ではないことを証明します。Myhill–Nerodeの定理は、無限に多くの区別可能な接頭辞を示すことで代替の議論を提供します。

非決定性オートマトンがより強力でないのなら、なぜそれらを使用するのですか？

それらはしばしばはるかに小さく、設計が容易であるか、正規表現から導出するのが簡単です。部分集合構成は、必要に応じてそれらを決定性形式に変換できますが、状態数において指数関数的なコストがかかる可能性があります。したがって、非決定性は認識能力の向上ではなく、便利な仕様ツールとして利用されます。