L ={0m1（n + m）2n|のプッシュダウンオートマトンを構築するC ++ではm、n =0}

言語「L」が与えられ、タスクは、与えられた言語のプッシュダウンオートマトンを構築することです。これは、1の出現が0と2の出現の追加になることを説明します。また、0と2の出現は最小であり、文字列を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 ^m 1 ^m − 01、0011、000111など。0の数はnoと同じです。 1の。 nが0の場合、2はありません。 0を押し続け、最初の1に遭遇したらすぐに、0をポップします。文字列の最後に到達し、0が残されていない場合、文字列は受け入れられます。

• 1 ⁿ 2 ⁿ − 12、1122、111222など。1の数はnoに等しい。 2秒の。 mが0の場合、0はありません。 1を押し続け、最初の2に遭遇したらすぐに、1をポップします。文字列の最後に到達し、1が残っていない場合、文字列は受け入れられます。

• 0 ⁿ 1 ^{m + n} 2 ^m − 0112、001112、001112など。1の数は数の合計に等しい。 0と2の。最初の1が検出されたらすぐに0を押し続け、0がなくなるまで0をポップします。ここで、最初の2が検出されるまで、もう一度1を押します。次に、2ごとに、1がなくなるまで1をポップし始めます。最後に到達し、1が残っていない場合、文字列は受け入れられます。

• NULL文字列も受け入れられます。 0 ⁰ 1 ⁰ 2 ⁰

機械を理解しましょう

• 状態q0の遷移-

  • （0、I / 0I）-スタックの最上位がIで、現在の入力シンボルが0の場合、0をスタックの最上位にプッシュしてq0のままにします。スタックは0Iになります...

  • （0、0/00）-スタックの最上位が0で、現在の入力シンボルも0の場合、0をスタックの最上位にプッシュしてq0のままにします。スタックは00になります...次の1または2まで0を押し続けます。

  • （1、I / 1I）-スタックの最上位がIで、現在の入力シンボルが1の場合、1をスタックの最上位にプッシュしてq1に移動します。スタックは1Iになります...

  • （1、0 / $）-スタックの最上位が0で、現在の入力シンボルが1の場合、0をポップしてq1に移動します。

  • （1、0 / $）-スタックの最上位が0で、現在の入力シンボルが1の場合、0をポップしてq1に移動します。

• 状態q1の遷移-

  • （1、1/11）-スタックの最上位が1で、現在の入力シンボルも1の場合、1をスタックの最上位にプッシュしてq1のままにします。スタックは11になります...次の0または2まで1を押し続けます。

  • （1、0 / $）-スタックの最上位が0で、現在の入力シンボルが1の場合、0をポップしてq1のままにします。

  • （$、I / I）-スタックの最上位がIで、入力がない場合は、何もせずにqfに移動します。

  • （2、1 / $）-スタックの最上位が1で、現在の入力シンボルが2の場合、1をポップしてq2に移動します。

• 状態q2の遷移-

  • （2、1 / $）-スタックの最上位が1で、現在の入力シンボルが2の場合、1をポップし、q2のままにします。

  • （$、I / I）-スタックの最上位がIで、入力がない場合は、何もせずにqfに移動します。