まずはPDAの定義から。PDAといっても、はてなキーワードにあるようなPersonal Data Assistantの略ではなく、Push Down Automatonのこと。PDA自体がε-NFA（イプシロンムーブ非決定性有限オートマトン）を拡張した概念なので、当然ながらスタックに関する定義が付け加わったに過ぎない。
例えば、遷移関数σが３変数の関数に拡張されている。つまりスタックの状態が遷移に影響するからである。また、この変数でεが指定されるとスタックがポップアップする。
次に受理状態の判定が２種類あるということが説明される。すなわち今まで通り、ワードをすべて処理した段階で受理状態に至るというものと、もうひとつスタックが完全になくなるというもの。しかし、この２つの方法によって受理できるワードのクラスは同じだということが証明される。すなわち便利だから２つの方法があるということだ。
これは直感的に理解できた。
難しくはない。むしろ易しいと言っていいと思う。ところで、オートマトンの状態には時点表示というのがあり、これを時系列に結ぶ記号が「├」という変わった記号（カタカナの「ト」のような記号）である。これを日本語で「回転扉」記法というらしい。英語ではなんとかとか言っていたが、扉は関係なかったような？（違っていたら指摘ください）
たしかに（最近話題の）回転扉に似ているけれど、どこからそんな訳がでてきたのだろうか？と不思議に思った。
