形式言語理論（けいしげんごりろん）

最終更新：2026/4/25

形式言語理論は、計算可能性の理論における、形式言語の性質や構造を数学的に研究する分野である。

別名・同義語計算可能性理論オートマトン理論

ポイント

オートマトン理論と密接に関連し、プログラミング言語の設計やコンパイラの開発に応用される。

概要

形式言語理論は、計算機科学の基礎をなす理論の一つであり、文字列の集合である「形式言語」を数学的に記述し、その性質を分析します。この理論は、コンピュータが理解し処理できる言語の構造を理解するために不可欠であり、プログラミング言語の設計、コンパイラの作成、自然言語処理など、幅広い分野に応用されています。

形式言語理論の起源は、20世紀初頭の数学者たちの研究に遡ります。アラン・チューリングによるチューリングマシンの概念や、アロンゾ・チャーチによるラムダ計算の導入などが、その基礎となりました。1950年代には、ノーム・チョムスキーが形式文法の階層構造を提唱し、形式言語理論の発展に大きく貢献しました。

チョムスキー階層は、形式文法の表現力と認識能力に基づいて、形式言語を4つのクラスに分類したものです。

タイプ0 (再帰的に列挙可能な言語): 最も一般的な形式言語であり、チューリングマシンで認識可能です。
タイプ1 (文脈依存言語): 文脈依存文法によって生成される言語であり、線形拘束オートマトンで認識可能です。
タイプ2 (文脈自由言語): 文脈自由文法によって生成される言語であり、プッシュダウンオートマトンで認識可能です。プログラミング言語の構文解析によく用いられます。
タイプ3 (正規言語): 正規文法によって生成される言語であり、有限オートマトンで認識可能です。テキスト検索やパターンマッチングなどに用いられます。

形式言語理論は、以下のような分野で応用されています。