プッシュダウンオートマトン(PDA)
詳細は割愛するが, 有限オートマトンにスタックをつけて履歴を記憶できるようにしたことで先程のような言語も受理することが出来るようになった. つまり有限オートマトンよりも表現力が高いといえる.
を受理するPDAのアイデア
スタックに入れる記号を x とする. a があるうちはひたすらスタックに x をプッシュしていき, b が来始めたらスタックから x を取り除いていく. 文字を全部読み終わった時にスタックが空だったら a と b は同じ文字数だったということになる.
文脈自由文法
プッシュダウンオートマトンの限界
しかし, プッシュダウンオートマトンにも限界が存在する. 例えば のような言語を受理するプッシュダウンオートマトンは作ることが出来ない.