形式言語

決められた記号の集まりと文法規則によって、どの記号列が正しい文かを厳密に定めた言語。チョムスキーの階層では、生成する文法の制約の強さにより、句構造言語、文脈依存言語、文脈自由言語、正規言語に分けられ、それぞれチューリング機械、線形拘束オートマトン、プッシュダウンオートマトン、有限オートマトンで受理される。プログラム言語の構文の定義（BNF）や正規表現の基礎である。

定められた記号の集合（アルファベット）と生成規則（文法）によって、どの記号列が正しい文かが厳密に決まる言語。正規言語や文脈自由言語などの階層があり、プログラミング言語の構文の定義、コンパイラの構文解析、正規表現などの理論的な基礎となる。