プッシュダウンオートマトン

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

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

アルゴリズムの実行に必要な時間や空間の量をオーダー記号O(n)で表現したもの。時間計算量と領域計算量があり、入力サイズnに対する増加傾向でアルゴリズムの効率を評価する。O(1)<O(log n)<O(n)<O(n log n)<O(n^2)<O(2^n)の順に計算量が大きい。

NPクラスに属し、かつNPクラスの全問題から多項式時間で帰着可能な問題の総称。効率的な（多項式時間の）解法が見つかっておらず、一つでも多項式時間で解ければP=NPが証明される。巡回セールスマン問題やナップサック問題が代表例。

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