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

言語「L」が与えられ、タスクは、0と3の出現が等しく、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 ⁿ 3 ⁿ − 03、0033、000333など。0の数はnoと同じです。 3秒の。 mが0の場合、1と2はありません。 0を押し続け、最初の3が検出されるとすぐに、0をポップします。文字列の最後に到達し、0が残されていない場合、文字列は受け入れられます。

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

• 0 ⁿ 1 ^m 2 ^m 3 ⁿ − 0123、001233、011223など。0の数はnoと同じです。 3秒と1秒の2秒に等しい。 0と1を押し続けます。最初の2が検出されるとすぐに、それが上にある場合は1をポップし、残りの3の場合は0をポップします。最後に到達し、0が残っていない場合、文字列は受け入れられます。

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

機械を理解しましょう

• 状態q0の遷移-

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

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

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

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

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

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

• 状態q1の遷移-

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

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

• 状態q2の遷移-

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

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

• 状態q3の遷移-

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

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

• 状態q5の遷移-

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

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

• 状態q6の遷移-

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

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