L = {0^(n+m)1^m2^n | m, n ≥ 0} のプッシュダウンオートマトンを構築する方法

言語「L」が与えられ、この言語に対するプッシュダウンオートマトン（PDA）を構築することが課題です。この言語は、記号0の出現回数が記号1と記号2の出現回数の合計に等しいことを表しています。また、1と2はそれぞれ最低1回出現しますが、文字列が空文字列（NULL）となる場合もあり、その場合もオートマトンに受理される必要があります。

プッシュダウンオートマトンとは？

プッシュダウンオートマトン（PDA）は、正規文法に対して決定性有限オートマトン（DFA）を設計するのと同じように、文脈自由文法を実装するための手法です。DFAは有限のデータしか扱えませんが、PDAは無限のデータを扱うことができます。プッシュダウンオートマトンは、「有限状態機械」と「スタック」を組み合わせたものと理解できます。

プッシュダウンオートマトンは次の3つの要素で構成されます。

• 入力テープ
• 制御ユニット
• 無限のサイズを持つスタック

PDAは形式的に7つ組（Q, Σ, S, δ, q0, I, F）として記述できます。

• Q：有限個の状態の集合
• Σ：入力アルファベット
• S：スタックシンボル
• δ：遷移関数 Q × (Σ ∪ {ε}) × S → Q × S*
• q0：初期状態（q0 ∈ Q）
• I：初期スタックトップシンボル（I ∈ S）
• F：受理状態の集合（F ⊆ Q）

与えられた言語に対するプッシュダウンオートマトンの構築

このPDAが受理できる文字列は、以下の形式になります。

• 0ⁿ2ⁿ の形式：02、0022、000222 など。0の個数と2の個数が等しくなります。mが0の場合、1は含まれません。0をスタックにプッシュし続け、最初の2が出現した時点で0をポップしていきます。文字列の終わりに到達したときにスタック上に0が残っていなければ、その文字列は受理されます。
• 0^m1^m の形式：01、0011、000111 など。0の個数と1の個数が等しくなります。nが0の場合、2は含まれません。0をスタックにプッシュし続け、最初の1が出現した時点で0をポップしていきます。文字列の終わりに到達したときにスタック上に0が残っていなければ、その文字列は受理されます。
• 0^n+m1^m2ⁿ の形式：0012、000112、000122 など。0の個数が1の個数と2の個数の合計に等しくなります。0をスタックにプッシュし続け、最初の1が出現したら、1がなくなるまで0をポップします。その後、再び0をプッシュし続け、最初の2が出現したら、2がなくなるまで0をポップします。これにより文字列は受理されます。
• 空文字列も受理されます：0⁰1⁰2⁰ に相当します。

機械の動作を理解する

状態 q0 の遷移

• ( 0, I/0I )：スタックのトップがIで、現在の入力記号が0の場合、0をスタックのトップにプッシュし、q0にとどまります。スタックは 0I... となります。
• ( 0, 0/00 )：スタックのトップが0で、現在の入力記号も0の場合、0をスタックのトップにプッシュし、q0にとどまります。スタックは 00... となります。次の1または2が現れるまで、0をプッシュし続けます。
• ( 1, 0/$ )：スタックのトップが0で、現在の入力記号が1の場合、0をポップしてq1へ遷移します。
• ( 2, 0/$ )：スタックのトップが0で、現在の入力記号が2の場合、0をポップしてq2へ遷移します。
• ( $, I/I )：スタックのトップがIで、入力がない場合は何もせずqfへ遷移します。これは空文字列に対応します。

状態 q1 の遷移

• ( 1, 0/$ )：スタックのトップが0で、現在の入力記号が1の場合、0をポップしてq1にとどまります。
• ( $, I/I )：スタックのトップがIで、入力がない場合は何もせずqfへ遷移します。
• ( 2, 0/$ )：スタックのトップが0で、現在の入力記号が2の場合、0をポップしてq2へ遷移します。

状態 q2 の遷移

• ( 2, 0/$ )：スタックのトップが0で、現在の入力記号が2の場合、0をポップしてq2にとどまります。
• ( $, I/I )：スタックのトップがIで、入力がない場合は何もせずqfへ遷移します。

以上のように、スタックを活用して0の個数を記録し、1と2の出現に応じて対応する数だけポップすることで、L = {0^n+m1^m2ⁿ | m, n ≥ 0} という言語を認識するプッシュダウンオートマトンを構築できます。