形式言語の階層

形式言語の階層

形式言語の階層は、計算理論や形式言語学における中心的な概念であり、さまざまな文法やオートマトンによって構成される言語クラスの相互関係を示しています。この階層は、主に1956年にノーム・チョムスキーによって発表されたチョムスキー階層に基づいており、その後の研究によりさらに詳細な分類が進められてきました。

包含階層

包含階層とは、異なる集合が階層における親子関係であり、上位の集合が下位のすべての集合を含む構造を指します。形式言語の階層はそれぞれ異なる言語クラスから成り立っており、上位クラスは下位クラスのすべての要素を包含しています。例えば、形式言語は形式文法やオートマトンを通じて定義され、その数学的特性によって各階層での位置付けが明らかにされます。

チョムスキー階層

チョムスキー階層は、生成文法を基本にした言語の階層であり、をタイプに分けて整理されています。具体的には以下のように分類されます。

• - タイプ-0 (無制限文法): 全ての書き換えが許される文法で、チューリングマシンが受理する言語。このクラスには帰納的可算言語が含まれ、チューリング受理性に基づいています。
• - タイプ-1 (文脈依存文法): 非終端記号に基づく書き換えが文脈に依存する文法で、これに該当する言語は文脈依存言語と呼ばれます。
• - タイプ-2 (文脈自由文法): 書き換えが文脈に依存しない文法で、文脈自由言語がこのカテゴリに含まれます。
• - タイプ-3 (正規文法): 最も制限の緩い文法であり、書き換えにおいて終端記号のみを含む言語が正規言語として定義されます。

これらの文法はそれぞれ上位の文法の真部分集合となっており、その関係性によって言語の階層も成立しています。

各タイプの詳細

タイプ-0

帰納的可算言語は、チューリングマシンが任意の入力文字列に対して受理または拒否することを保証しない言語です。これに対して決定性が求められるのが帰納言語で、チューリングマシンが常に停止することが保証されるクラスです。これらは計算複雑性と関連し、異なるアルゴリズムの実行時間に応じて異なる複雑性クラスに振り分けられます。

タイプ-1

文脈依存言語は、特定の文脈や環境に依存して生成ルールが適用される性質を持ちます。このクラスの言語は日常的にはあまり用いられないものの、音韻論の例などに見ることができます。また、Indexed Languages（IL）や弱文脈依存言語といった重要なサブクラスも存在します。

タイプ-2

文脈自由言語は、文脈に依存せずに生成規則が適用される言語であり、自然言語処理やプログラミング言語の文法の基礎に多く使われています。

タイプ-3

この層では、空集合や有限集合等、最も基本的な形式言語が定義されます。

まとめ

形式言語の階層は、計算理論における根幹を成す概念です。これにより、さまざまな言語の構造や性質、相互の関係が明確になり、計算機科学や言語学の研究において非常に重要な役割を果たします。

もう一度検索