プッシュダウン・オートマトン
プッシュダウンオートマトンは通常の有限オートマトンとは以下の二点で異なる。
スタックのトップを使って成すべき状態遷移を判断する。
遷移実行の一部としてスタック操作を行うことが出来る。
プッシュダウン・オートマトンは入力信号、現在状態、スタックのトップを使って状態遷移表内の位置を指定することで遷移先を選択する。通常の有限オートマトンは現在状態と入力信号しかなく、スタックは持たない。プッシュダウン・オートマトンはスタックを遷移先選択のパラメータに加える。つまり、入力信号と現在状態とスタックのトップにある文字から遷移先を選択する。
プッシュダウン・オートマトンは、遷移を実行する動作の一部としてスタックを操作することもできる。通常の有限オートマトンは遷移の結果として新しい状態を選択する。スタック操作とはある特定の文字をスタックにプッシュすることやスタックのトップをポップすることを意味する。また、プッシュダウン・オートマトンはスタックを操作せずにそのままにしておくこともできる。