L ={a（2 * m）c（4 * n）dnbm|のプッシュダウンオートマトンを作成するC ++ではm、n =0}

言語「L」が与えられ、タスクは、文字「a」の出現が出現時間を2倍にする必要があることを説明する、指定された言語のプッシュダウンオートマトンを構築することです。文字「b」と文字「c」の出現は「d」の4倍である必要があり、すべての文字の出現は最小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で受け入れられる文字列は、-

• c ⁴ⁿ d ⁿ − ccccd、ccccccccddなど。csの数はnoの4倍です。 dsの。 mが0の場合、asとbsはありません。 csを押し続け、最初のdに遭遇したらすぐに、スタックから4cをポップします。文字列の最後に到達し、csがないままになっている場合、文字列は受け入れられます。

• a ^2m b ^m − aab、aaaabbなど。そのままの数は2倍です。 bsの。 nが0の場合、csとdsはありません。最初のbに遭遇したらすぐに押し続け、スタックから2bをポップします。文字列の最後に到達し、そのままにしておくと、文字列が受け入れられます。

• a ^2m c ⁴ⁿ d ⁿ b ^m − aaccccdb、aaaaccccccccddbb。そのままの数は2倍です。 dsの数の4倍に等しいbsとcsの数。 asとcsを押し続けます。最初のdに遭遇したらすぐに、それが上にある場合は4 csをポップし、残りのbsについては2をポップします。最後に到達し、aが残っていない場合、文字列は受け入れられます。

• NULL文字列も受け入れられます。 a ⁰ c ⁰ d ⁰ b ⁰ 。

機械を理解しましょう

• 状態q0の遷移-

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

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

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

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

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

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

  • （d、c / e、cccc）-スタックの最上位がcで、現在の入力シンボルがdの場合、スタックから4 dsポップして、q4に移動します。

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

• 状態q1の遷移-

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

  • （d、c / e、cccc）-スタックの最上位がcで、現在の入力シンボルがdの場合、スタックから4 dsポップして、q2に移動します。

• 状態q2の遷移-

  • （d、c / e、cccc）-スタックの最上位がcで、現在の入力シンボルがdの場合、スタックから4 dsポップして、q2に移動します。

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

• 状態q3の遷移-

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

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

• 状態q4の遷移-

  • （d、c / e、cccc）-スタックの最上位がcで、現在の入力シンボルがdの場合、スタックから4 dsポップし、q4のままにします。

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