C++
 Computer >> コンピューター >  >> プログラミング >> C++

L = {0^m 1^(n+m) 2^n | m, n ≥ 0} を認識するプッシュダウンオートマトン（PDA）の構築方法

言語「L = {0m1(n+m)2n | m, n ≥ 0}」が与えられ、この言語を認識するプッシュダウンオートマトン（PDA）を構築することが課題です。この言語では、「1の出現回数が0の出現回数と2の出現回数の合計に等しい」という条件が定められています。さらに、mとnは0以上であるため、0や2が出現しないケースも許容され、文字列が空（NULL）となる場合もオートマトンによって受理されなければなりません。

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

プッシュダウンオートマトン（Pushdown Automata：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）

与えられた言語に対するプッシュダウンオートマトンの構築

L = {0^m 1^(n+m) 2^n | m, n ≥ 0} を認識するプッシュダウンオートマトン（PDA）の構築方法

このPDAが受理する文字列は、以下のような形式になります。

  • 0m1m ― 「01」「0011」「000111」など。0の個数と1の個数が等しいパターンです。nが0の場合、2は出現しません。まず0を読みながらスタックにプッシュし続け、最初の1に出会った時点で0をポップしていきます。文字列の末尾に到達したときにスタックに0が残っていなければ、その文字列は受理されます。
  • 1n2n ― 「12」「1122」「111222」など。1の個数と2の個数が等しいパターンです。mが0の場合、0は出現しません。まず1を読みながらスタックにプッシュし続け、最初の2に出会った時点で1をポップしていきます。文字列の末尾に到達したときにスタックに1が残っていなければ、その文字列は受理されます。
  • 0n1(m+n)2m ― 「0112」「001112」など。1の個数が0の個数と2の個数の合計に等しいパターンです。まず0をプッシュし続け、最初の1に出会ったら0がなくなるまでポップします。次に、最初の2に出会うまで1をプッシュします。その後、各2について1をポップし、1がなくなるまで繰り返します。文字列の末尾に到達して1が残っていなければ、その文字列は受理されます。
  • NULL文字列も受理されます（001020に相当）。mとnがともに0の場合、空文字列となり、これも有効な入力として扱われます。

マシンの動作を詳しく見る

状態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へ移行します。

状態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へ移行します。

まとめ

このPDAは、スタックを活用することで「1の個数 ＝ 0の個数 ＋ 2の個数」という文脈自由言語特有の条件を検証します。状態q0では0の読み込みとカウント、状態q1では0との対応確認および1のカウント、状態q2では2との対応確認をそれぞれ担当し、最終的にスタックが初期記号Iのみに戻った時点で受理状態qfへ遷移することで、入力文字列の妥当性を判定します。

  1. L = {aⁱbʲcᵏ | i × j = k、i, j, k ≥ 1} を受理するチューリングマシンの構築方法

    本記事では、言語 L = {aⁱbʲcᵏ | i × j = k、i, j, k ≥ 1} に対応するチューリングマシンの構築方法を解説します。この言語は、A・B・C の3種類の記号のみからなる文字列のうち、「A の個数(i)と B の個数(j)の積が C の個数(k)と一致する」という条件を満たすものの集合を表しています。 受理される文字列の例 例えば、w = AABBBBCCCCCCCC という入力文字列を考えてみましょう。この場合、A が2個、B が4個、C が8個含まれており、2 × 4 = 8 という関係が成立しているため、このチューリングマシンはこの文字列を受理します。 構築のアプ

  2. DAG（有向非巡回グラフ）のランダム線形拡張を生成するC++プログラム

    この記事では、有向非巡回グラフ（DAG: Directed Acyclic Graph）のランダム線形拡張（Random Linear Extension）を作成する方法を解説します。線形拡張とは、DAGの位相ソート（トポロジカルソート）に相当するものです。以下のようなグラフを例に考えてみましょう。トポロジカルソートとは有向非巡回グラフにおけるトポロジカルソートとは、頂点を線形に並べた順序のことです。有向グラフのすべての辺 u-v に対して、並び順の中で頂点 u が必ず頂点 v よりも先に現れるような順序を指します。始点の頂点は必ず終点の頂点よりも先に配置される必要があるため、処理済みの頂点を