オートマトン

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

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

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

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

有限個の状態と状態遷移規則からなる計算モデル。決定性（DFA）と非決定性（NFA）があり、正規言語を認識する能力を持つ。状態遷移図や状態遷移表で表現され、字句解析やパターンマッチングに応用される。

有限オートマトンにスタック（プッシュダウンスタック）を追加した計算モデル。文脈自由言語を認識する能力を持ち、プログラミング言語の構文解析（括弧の対応や再帰構造の処理）に対応する。

任意のプログラムと入力に対して、そのプログラムが有限時間内に停止するかどうかを判定するアルゴリズムは存在しないことを証明した問題。チューリングによる証明は計算可能性理論の基礎であり、決定不能問題の代表例。