形式言語

文法規則によって、どの文字列が正しいかを厳密に定義した言語。BNFなどで規則を書き表す。日本語のようなあいまいさがないため、プログラム言語の構文定義やコンパイラの解析理論の基礎になる。

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

入力の記号を1つずつ読み、現在の状態と入力に応じて次の状態に遷移する抽象的な計算モデル。状態の数が有限の有限オートマトンは正規言語（正規表現で表せる記号列）を受理でき、字句解析や文字列のパターン照合に使われる。スタックを持つプッシュダウンオートマトンは文脈自由言語を受理し、構文解析の理論的な基礎になる。