0

決定論的有限オートマトンをプッシュ ダウン オートマトンに変換するアルゴリズムを探しています。

どんな助けでも感謝します。

ありがとう！

4

4 に答える 4

3

DFA の PDA バージョンは、各状態遷移がスタックに何もプッシュせず、スタックから何もポップしないことを除いて、同じように見えます。

于 2011-05-19T04:14:41.217 に答える
1

PDA は DFA の拡張機能であり、追加機能は 1 つだけです: スタック。PDA の遷移はトリプル (現在の状態、入力、スタックの一番上の要素) によって決定されるため、DFA の遷移はタプル (現在の状態、入力) によって決定されます。唯一の違いは、スタックの一番上にある要素です。eタプルをトリプル(空の文字列)に変換することで、DFA のすべてのトランジションを変換できます。スタックの一番上に要素として挿入されます。

そして、状態を変更した後、e(空の文字列) をスタックにプッシュします。

于 2011-07-27T12:42:00.557 に答える
0

他の誰かが見た場合に備えて、この古い質問に答えています。

DFA から PDA への変換は、スタックを追加するだけで簡単に自動化できます。ただし、DFA のセマンティクスが変更される可能性があり、そのように手動で変更した後、状態の数が少ない PDA になる可能性があります。私は最近この問題に直面しました。ややこのように、

システム (コンパイラなどではない) では、以前に作成されたコードは、何らかの理由で DFA を使用して作成されました。ユーザーがさまざまな関数を使用してコードを進めると、遷移が発生します。しばらくして、任意の順序で使用できる新しいトランジション関数のセットが到着しました。また、これらの新しい関数のいずれかの後の状態は、これらの関数のいずれかによって以前の状態に戻る可能性があります。FST を使用してこれを解決する唯一の方法は、大量の作業を伴うこの動作をサポートするために多数の新しい状態を追加することでした。しかし、代わりに、DFA から PDA に変更しました。スタックは遷移を非常にうまく追跡し、問題ははるかに少ない数の状態で解決されます。実際には、N 個の状態を追加するだけで済みました。ここで、N は到着した新しい関数の数です。

誰かがこの種のプロセスを簡単に自動化できるかどうかはわかりません。しかし、誰かがそれについて興味を持っている場合に備えて、そこに行きます.

于 2013-01-08T15:16:17.863 に答える
-1

ウィキペディアの記事によると

プッシュダウン オートマトンは、次の 2 つの点で有限状態マシンとは異なります。

  1. スタックの一番上を使用して、どのトランジションを取るかを決定できます。
  2. トランジションの実行の一部として、スタックを操作できます。

プッシュダウン オートマトンは、入力信号、現在の状態、およびスタックの一番上にあるシンボルによってテーブルにインデックスを付けることにより、遷移を選択します。これは、これら 3 つのパラメーターが、選択される遷移パスを完全に決定することを意味します。有限ステート マシンは、入力信号と現在の状態を確認するだけです。動作するスタックはありません。プッシュダウン オートマトンは、選択のためのパラメーターとしてスタックを追加します。

...
プッシュダウン オートマトンは文脈自由文法と同等です。すべての文脈自由文法に対して、文法によって生成された言語がオートマトンによって生成された言語と同一であるように、プッシュダウン オートマトンが存在します。これは簡単に証明できます。証明するのはより困難ですが、その逆が当てはまります。すべてのプッシュダウン オートマトンには、オートマトンによって生成される言語が文法によって生成される言語と同一であるような文脈自由文法が存在します。

于 2011-03-13T00:10:58.437 に答える