オートマトン

入力に応じて状態が遷移する抽象的な計算モデル。有限オートマトンは有限個の状態を持ち、正規言語の認識に対応する。状態遷移表や状態遷移図で動作を表現する。コンパイラの字句解析などに応用される。

プログラム言語などの形式言語の文法を記述するためのメタ言語。非終端記号、終端記号、生成規則で構成され、言語の構文規則を厳密に定義できる。コンパイラの構文解析で使用される。

文字列のパターンを表現するための記法。特殊文字（メタキャラクタ）を使って文字列の検索・置換・抽出を行う。正規言語に対応し、有限オートマトンで認識できる。

演算子を被演算子の後に記述する数式の表記法。後置記法とも呼ばれる。例えば「A+B」は「AB+」と書く。括弧が不要で、スタックを使って効率的に計算できるため、コンパイラの中間表現に使われる。

システムを有限の状態遷移モデルとして表し、到達しうるすべての状態を網羅的に調べて、満たすべき性質（デッドロックが起きないなど）が成り立つかを自動的に検証する手法。テストでは再現しにくい並行処理の不具合を見つけられ、性質が成り立たない場合はそこに至る手順を反例として示す。

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