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

言語「L」が与えられ、タスクは、与えられた言語のプッシュダウンオートマトンを構築することです。これは、0の出現が1と2の出現の追加になることを説明します。また、1と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で受け入れられる文字列は、-

• 1. 0 ⁿ 2 ⁿ ：02、0022、000222など。0の数はnoと同じです。 2秒の。 mが0の場合、1はありません。 0を押し続け、最初の2が検出されたらすぐに、0をポップします。文字列の最後に到達し、0が残されていない場合、文字列は受け入れられます。

• 0 ^m 1 ^m ：01、0011、000111など。0の数はnoと同じです。 1の。 nが0の場合、2はありません。 0を押し続け、最初の1に遭遇したらすぐに、0をポップします。文字列の最後に到達し、0が残されていない場合、文字列は受け入れられます。

• 0 ^{n + m} 1 ^m 2 ⁿ ：0012、000112、000122など。0の数は数の合計に等しい。 1秒と2秒の。 0を押し続け、最初の1に遭遇したら、1がなくなるまでそれらの0をポップします。次に、もう一度0を押し続け、最初の2が検出されたら、2がなくなるまでそれらの0をポップします。文字列が受け入れられます。

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

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

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

• 状態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に移動します。