pushdown-automaton - PDAの正式な説明

Question

FSM の正式な記述方法は覚えていますが、PDA の記述方法は少し異なります。丸で囲んだ部分を説明できる人はいますか？私は通常、よくメモを取りますが、ノートや他の場所でこれについて何かを見つけることができないようです. どんな助けでも大歓迎です。

Answer 1

プッシュ ダウン オートマトンの作業中は、グラフィカルと瞬時の 2 つのタイプがあります。
グラフィカル PDA では、スタック操作を図式的に示します。
瞬間的な PDA では、瞬間的なルールを使用します。
あなたの丸で囲んだ部分は後のカテゴリーに属します。
これらは次のことを意味するルールです:
開始する前に、最初にスタックにイプシロン値があることを明確にしてください。また、すべてのプッシュに対して、対応するポップ操作が存在する可能性があります。
つまり、最初の行では ((S,a,E),(S,a)) -> 最初のアルファベット a が入力されると、状態は同じままで、出力は a になります。また、入力が状態である限り、同じままです。
2 行目 ((S,b,a),(f,E)) -> このルールは、a の後に入力として b アルファベットがある場合、状態が変化し、a がポップアウトされ、他のアルファベットではなくS を使用して変化の状態を示すことができ、値はイプシロンになります。
最後の行では、入力が再び b であるため、状態は同じままであることが示されています。