L={0ⁿ1ᵐ2ᵐ3ⁿ|m, n ≥ 0}を受理するプッシュダウンオートマトン(PDA)の構築方法

言語「L」が与えられ、この言語を受理するプッシュダウンオートマトン(PDA)を構築することが課題です。この言語は、0の出現回数と3の出現回数が等しく、1の出現回数と2の出現回数も等しい文字列の集合を表します。さらに、mとnは0以上であるため、すべての記号の出現回数が0となる空文字列(NULL)も受理されなければなりません。

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

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

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

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

PDAは形式的に7つ組(Q, Σ, S, δ, q₀, I, F)で記述できます。

• Q: 有限個の状態の集合
• Σ: 入力アルファベット
• S: スタック記号の集合
• δ: 遷移関数 Q × (Σ ∪ {ε}) × S → Q × S*
• q₀: 初期状態(q₀ ∈ Q)
• I: 初期スタックトップ記号(I ∈ S)
• F: 受理状態の集合(F ⊆ Q)

与えられた言語に対するPDAの構築

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

• 0ⁿ3ⁿ — 03、0033、000333など。0の個数と3の個数が等しくなります。mが0の場合、1と2は含まれません。0を読み込むたびにスタックへプッシュし、最初の3が出現した時点から0をポップしていきます。文字列の末尾に達したときにスタックに0が残っていなければ、その文字列は受理されます。

• 1^m2^m — 12、1122、111222など。1の個数と2の個数が等しくなります。nが0の場合、0と3は含まれません。1を読み込むたびにスタックへプッシュし、最初の2が出現した時点から1をポップしていきます。文字列の末尾に達したときにスタックに1が残っていなければ、その文字列は受理されます。

• 0ⁿ1^m2^m3ⁿ — 0123、001233、011223など。0の個数と3の個数が等しく、1の個数と2の個数も等しくなります。まず0と1を順にプッシュしていき、最初の2が出現したらスタックトップの1をポップし、続く3に対しては0をポップします。文字列の末尾に達したときに0が残っていなければ、その文字列は受理されます。

• NULL文字列も受理されます。これは0⁰1⁰2⁰3⁰に相当します。

状態遷移の詳細

状態q0の遷移

• (0, I/0I) — スタックトップがIで、現在の入力記号が0の場合、0をスタックトップにプッシュし、q0にとどまります。スタックは0I…となります。

• (0, 0/00) — スタックトップが0で、現在の入力記号も0の場合、0をスタックトップにプッシュし、q0にとどまります。スタックは00…となります。次の1または3が現れるまで0をプッシュし続けます。

• (1, 0/10) — スタックトップが0で、現在の入力記号が1の場合、1をスタックトップにプッシュし、q1へ遷移します。スタックは10…となります。

• (1, I/1I) — スタックトップがIで、現在の入力記号が1の場合、1をプッシュし、q5へ遷移します。

• (3, 0/ε) — スタックトップが0で、現在の入力記号が3の場合、0をポップし、q3へ遷移します。

• ($, I/I) — スタックトップがIで、入力がもうない場合、何もせずq4へ遷移します。NULL文字列に対応する遷移です。

状態q1の遷移

• (1, 1/11) — スタックトップが1で、現在の入力記号も1の場合、1をスタックトップにプッシュし、q1にとどまります。スタックは11…となります。次の2が現れるまで1をプッシュし続けます。

• (2, 1/ε) — スタックトップが1で、現在の入力記号が2の場合、1をポップし、q2へ遷移します。

状態q2の遷移

• (2, 1/ε) — スタックトップが1で、現在の入力記号が2の場合、1をポップし、q2にとどまります。

• (3, 0/ε) — スタックトップが0で、現在の入力記号が3の場合、0をポップし、q3へ遷移します。

状態q3の遷移

• (3, 0/ε) — スタックトップが0で、現在の入力記号が3の場合、0をポップし、q3にとどまります。

• ($, I/I) — スタックトップがIで、入力がもうない場合、何もせずq4へ遷移します。これにより文字列が受理されます。

状態q5の遷移

• (1, 1/11) — スタックトップが1で、現在の入力記号も1の場合、1をスタックトップにプッシュし、q5にとどまります。スタックは11…となります。次の2が現れるまで1をプッシュし続けます。

• (2, 1/ε) — スタックトップが1で、現在の入力記号が2の場合、1をポップし、q6へ遷移します。

状態q6の遷移

• (2, 1/ε) — スタックトップが1で、現在の入力記号が2の場合、1をポップし、q6にとどまります。

• ($, I/I) — スタックトップがIで、入力がもうない場合、何もせずq4へ遷移します。これにより文字列が受理されます。

このように、スタックを活用して0と3、1と2の対応関係を記憶することで、文脈自由言語であるL={0ⁿ1^m2^m3ⁿ|m, n ≥ 0}を正確に認識するプッシュダウンオートマトンが実現できます。