概要

形式言語とは、指定された有限集合の記号、すなわちアルファベットから作られる有限列（文字列）の集まりである。数学、計算機科学、言語学では、式、プログラム、証明、そして自然言語の単純化モデルを厳密に記述するための枠組みとして用いられる。通常は言語をLやℒのような変数で表し、それが単一の式ではなく文字列の集合であることを強調する。これは形式体系における変数の扱いとも関係がある。

構造と主な特徴

あらゆる形式言語は、アルファベットと生成規則を基盤として成り立つ。重要な構成要素と性質は次のとおりである。

  • アルファベット：文字列を構成する有限個の記号の集合。
  • 文字列：記号の有限列。通常は空文字列も含まれる。
  • 文法または生成規則：どの文字列がその言語に属するかを定める統語規則。
  • 意味論：言語が何らかの体系をモデル化する場合に、文字列へ意味を与える任意の対応づけ。たとえば、プログラミング言語や論理計算体系で用いられる。

種類と分類

形式言語は、それを生成または認識する文法や機械の種類によって分類される。古典的な区分には、正規言語、文脈自由言語、文脈依存言語、再帰的可算言語がある。この分類はオートマトン理論とチョムスキー階層の基礎をなし、文法を有限オートマトン、プッシュダウン・オートマトン、チューリング機械などの計算モデルと結びつける。

歴史と発展

形式言語の考え方は、数学者や論理学者が曖昧さやパラドックスを避けるために、厳密な記号体系を求めたことから発展した。20世紀半ばの発展により、文法に基づく記述は抽象機械と結びつき、現代の形式言語理論が成立した。これらはプログラミング言語設計やコンパイラ構築にも応用され、論理、計算可能性、そして統語の数学的研究にその起源をもつ。

用途、例、重要性

形式言語は多くの分野で中心的な役割を果たす。例と応用には次のようなものがある。

  • プログラミング言語とコンパイラの仕様化および実装。
  • 自然言語研究や計算言語学における統語構造のモデル化。
  • 論理的推論や検証で用いられる形式論理と証明体系の定義。
  • 正規表現のような道具で検索可能、または決定可能なパターン集合を記述すること。

区別と注目すべき点

形式言語は自然言語と比べて、記号と生成規則が明示的に定められている点で精密である。そのため、文字列は曖昧さのない統語的地位を持ち、意味論が与えられる場合には意味も明確になる。この精密さは日常会話に多い曖昧さを減らし、あるいは排除するが、形式文法の中にはなお曖昧な導出を許すものもある。どの言語特性が決定可能か、あるいは効率的に決定可能かを調べることは、理論計算機科学と論理学の重要な主題である。