オートマトンと形式言語

オートマトンと形式言語理論は、能力を増していく理想化された機械と、それぞれの機械が認識できる文字列のクラス、すなわち言語を研究する学問分野であり、パターンとして何が数えられるのか、そしてそれを検出するために何が必要なのかについて、厳密な数学的説明を与えるものです。

Definition

形式言語とは、固定されたアルファベット上の有限文字列の集合であり、オートマトンとは、その受理計算がそのような言語を定義する抽象的な計算装置です。この分野は、言語を生成または認識する最も単純な種類のオートマトンまたは文法によって言語を分類します。

Scope

この分野は、有限オートマトンと正規言語、プッシュダウンオートマトンと文脈自由言語、文法と機械モデルを関連付けるチョムスキー階層、言語クラスの閉包特性と決定特性、無限語と木を処理するオートマトン、およびそれらに付随する代数的・論理的特徴付けを扱います。

Sub-topics

• Automata on Infinite Objects
• Context-Free Languages and Pushdown Automata
• Finite Automata and Regular Languages
• The Chomsky Hierarchy

Core questions

• 有限メモリを持つ機械はどの言語を認識でき、どの言語を認識できないのか？
• チョムスキー階層の各レベルにおいて、文法と機械モデルはどのように対応しているのか？
• 空性や等価性など、言語クラスに関するどの問題がアルゴリズム的に決定可能であるか？
• オートマトンは無限語や木にどのように拡張され、なぜこれが検証にとって重要なのか？

Key theories

決定性有限オートマトンと非決定性有限オートマトンの等価性

すべての非決定性有限オートマトンは、部分集合構成法によって同じ言語を受理する決定性有限オートマトンに変換できるため、非決定性は有限状態レベルでは認識能力を追加しないが、指数関数的に簡潔になる可能性がある。

クリーネの定理

有限オートマトンによって認識される言語は、正規表現によって記述される正規言語と正確に一致し、最も単純な言語クラスの機械的、代数的、文法的な見方を結びつけるものである。

チョムスキー階層

正規言語、文脈自由言語、文脈依存言語、帰納的可算言語は厳密な包含関係の連鎖を形成し、各レベルは文法タイプと対応するメモリ構造を持つオートマトンモデルに一致する。

Clinical relevance

有限オートマトンと正規表現は、コンパイラの字句解析、テキスト検索、プロトコル仕様において強力な役割を果たし、文脈自由文法はプログラミング言語の構文解析の基礎となります。無限オブジェクト上のオートマトンは、システムが時相論理仕様に対して検証されるモデル検査のアルゴリズム的核を形成します。

History

有限状態モデルは、1940年代のマカロックとピッツのニューラルネットワークから生まれ、1951年頃にクリーネによって言語理論的な形式が与えられました。ラビンとスコットは1959年に非決定性オートマトンを導入し、一方、1950年代後半のチョムスキーの文法は、言語クラスを現在もこの主題を構造化している階層に組織化しました。

Key figures

• Stephen Kleene
• Michael Rabin
• Dana Scott
• Noam Chomsky

Seminal works

• rabinScott1959
• sipser2013
• hopcroft2006

Frequently asked questions

有限オートマトンはなぜバランスの取れた括弧を認識できないのですか？

任意の深さの入れ子を認識するには、まだ対応が取れていない開き括弧の数を数える必要があり、これは任意の固定された状態数を超える可能性があります。有限オートマトンは限られたメモリしか持たないため、この計数能力はプッシュダウンオートマトンと文脈自由言語という一つ上のレベルに属します。

形式言語理論の実用的な利点は何ですか？

形式言語理論は、特定のツールがどのパターンを表現できるかをエンジニアに伝えます。正規表現はトークンには十分ですが、入れ子構造には不十分です。そのため、コンパイラは正規表現レキサーと文脈自由パーサーの間で作業を分割し、検証ツールは無限語上のオートマトンに依存しています。