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

L = {a²ᵐc⁴ⁿdⁿbᵐ | m, n ≥ 0} に対するプッシュダウンオートマトンの構築方法

ここでは言語「L」が与えられ、この言語に対応するプッシュダウンオートマトン（PDA）を構築することが課題となります。この言語は、文字「a」の出現回数が文字「b」の出現回数のちょうど2倍であり、文字「c」の出現回数が文字「d」の出現回数のちょうど4倍であることを意味しています。また、m と n は 0 以上であるため、m = 0 かつ n = 0 の場合には文字列が NULL（空文字列）になりますが、この空文字列もオートマトンによって受理される必要があります。

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

プッシュダウンオートマトン（Pushdown Automata / PDA）は、正規文法に対して決定性有限オートマトン（DFA）を設計するのと同じように、文脈自由文法を実装するための手法です。DFA は有限データしか扱えませんが、PDA は無限のデータも扱うことができます。PDA は「有限状態機械」と「スタック」を組み合わせたものと考えると理解しやすいでしょう。

プッシュダウンオートマトンは、次の3つの要素で構成されています。

  • 入力テープ
  • 制御ユニット
  • 無限のサイズを持つスタック

PDA は、次の7つ組（7-tuple）(Q, Σ, S, δ, q0, I, F) として形式的に定義できます。

  • Q：有限個の状態の集合
  • Σ：入力アルファベット
  • S：スタックシンボル
  • δ：遷移関数 Q × (Σ ∪ {ε}) × S → Q × S*
  • q0：初期状態（q0 ∈ Q）
  • I：初期スタックトップシンボル（I ∈ S）
  • F：受理状態の集合（F ⊆ Q）

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

L = {a²ᵐc⁴ⁿdⁿbᵐ | m, n ≥ 0} に対するプッシュダウンオートマトンの構築方法

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

  • c4ndn ── ccccd、ccccccccdd など。c の数が d の数の4倍になる文字列です。m = 0 の場合は a と b は現れません。c をスタックにプッシュし続け、最初の d が出現した時点でスタックから c を4つポップします。文字列の末尾に到達したときにスタックに c が残っていなければ、その文字列は受理されます。
  • a2mbm ── aab、aaaabb など。a の数が b の数の2倍になる文字列です。n = 0 の場合は c と d は現れません。a をスタックにプッシュし続け、最初の b が出現した時点でスタックから a を2つポップします。文字列の末尾に到達したときにスタックに a が残っていなければ、その文字列は受理されます。
  • a2mc4ndnbm ── aaccccdb、aaaaccccccccddbb など。a の数が b の数の2倍、c の数が d の数の4倍になる文字列です。a と c をスタックにプッシュし続け、最初の d が出現したら、トップにある c を4つポップします。その後、残りの b に対応して a を2つずつポップしていきます。文字列の末尾に到達したときに a が残っていなければ、その文字列は受理されます。
  • NULL 文字列 も受理されます。これは a0c0d0b0 に相当します。

機械の動作を理解する

次に、各状態における遷移規則を詳しく見ていきましょう。

状態 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 が来るまで a をプッシュし続けます。
  • ( c, c / c, c ) ── スタックのトップが c で、現在の入力記号も c のとき、c をさらにプッシュして q0 に留まります。スタックは cc… となります。次の d が来るまで c をプッシュし続けます。
  • ( b, a / ε, a ) ── スタックのトップが a で、現在の入力記号が b のとき、スタックから a を2つポップして q3 へ移行します。
  • ( c, a / c, a ) ── スタックのトップが a で、現在の入力記号が c のとき、c をスタックのトップにプッシュして q1 へ移行します。スタックは ca… となります。
  • ( d, c / ε, c ) ── スタックのトップが c で、現在の入力記号が d のとき、スタックから c を4つポップして q4 へ移行します。
  • ( $, I / I, I ) ── スタックのトップが I で、入力がもうないとき、何もせずに q5 へ移行します。これは NULL 文字列を受理するための遷移です。

状態 q1 の遷移

  • ( c, c / c, c ) ── スタックのトップが c で、現在の入力記号も c のとき、c をさらにプッシュして q1 に留まります。スタックは cc… となります。次の d が来るまで c をプッシュし続けます。
  • ( d, c / ε, c ) ── スタックのトップが c で、現在の入力記号が d のとき、スタックから c を4つポップして q2 へ移行します。

状態 q2 の遷移

  • ( d, c / ε, c ) ── スタックのトップが c で、現在の入力記号が d のとき、スタックから c を4つポップして q2 に留まります。
  • ( b, a / ε, a ) ── スタックのトップが a で、現在の入力記号が b のとき、スタックから a を2つポップして q3 へ移行します。

状態 q3 の遷移

  • ( b, a / ε, a ) ── スタックのトップが a で、現在の入力記号が b のとき、スタックから a を2つポップして q3 に留まります。
  • ( $, I / I, I ) ── スタックのトップが I で、入力がもうないとき、何もせずに q5 へ移行します。NULL 文字列を受理するための遷移です。

状態 q4 の遷移

  • ( d, c / ε, c ) ── スタックのトップが c で、現在の入力記号が d のとき、スタックから c を4つポップして q4 に留まります。
  • ( $, I / I, I ) ── スタックのトップが I で、入力がもうないとき、何もせずに q5 へ移行します。NULL 文字列を受理するための遷移です。

まとめ

このように、スタックを活用することで、a と b の出現回数の関係（2対1）、および c と d の出現回数の関係（4対1）を数え上げて検証することができます。有限オートマトンでは実現できないこの種のカウント処理こそが、プッシュダウンオートマトンの本質的な強みです。m と n がともに 0 の場合の空文字列も含めて、言語 L に属するすべての文字列をこの PDA は正しく受理します。

  1. C++ STLのスタック（stack）徹底解説！LIFO構造の基本操作とサンプルコード

    C++ STLにおけるスタック（stack）は、LIFO（Last In First Out：後入れ先出し）構造として実装されるコンテナです。LIFOとは「最後に入れたものが最初に取り出される」という意味で、本を一冊ずつ積み上げた山をイメージすると理解しやすいでしょう。一番上に置いた本（＝最後に挿入された要素）が最初に取り出されることから、この構造はLIFOと呼ばれています。 スタックで使える主な操作 1. top() – 最上位要素の取得 スタックの最上位（先頭）にある要素への参照を返します。要素自体は削除されません。 構文：name_of_stack.top() 引数：なし 戻り値：ス

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

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