言語を受け入れるプッシュダウンオートマトンを作成するには？

Question

この言語のプッシュダウンオートマトンを作成する方法を教えてもらえますか？あなたはそれが素晴らしいと私は説明することができる場合、私は言語のための設定表記を理解していません。ありがとうございます

Answer 1

表記とは、n文字aとそれに続く文字bで始まるすべての単語で構成される言語です。更に、数n及びmは等しくてはならない。

PDAでこれを受け入れる明白な方法は、次のとおりです。最初から、あなたが読んだすべてのものについて、1つをスタックに置きます。あなたがbを見始めると、あなたはあなたがスタックからaの1つを取り除くごとに読む。最後のbが最後のスタックシンボルを取り除く場合、n = mであり、PDAは拒絶すべきである。それ以外の場合は、単語がbの場合は受け入れる必要があります。