10

与えられた 2 つの DFA の結合を構築するためのアルゴリズムの簡単な説明を誰かが持っていますか? たとえば、{0,1} に 2 つの DFA があるとします。

{w|w has an odd number of characters}
  w has states A and B

delta | 0  | 1
----------------
  A   | B  | B
----------------
  B   | A  | A


{x|x has an even number of 1s}
  x has states a and b

delta | 0  | 1
----------------
  a   | a  | b
----------------
  b   | b  | a

ユニオンを次のように示す結果の遷移テーブルがあります。

delta | 0  | 1 
----------------
  Aa  | Ba | Bb
----------------
  Ab  | Bb | Ba
----------------
  Ba  | Aa | Ab
----------------
  Bb  | Ab | Aa

講義ノートに解決策の図を載せていますが、他の人がそれをどのように説明するかを知りたいです。このことから、状態値を使用してこれら 2 つの元のテーブルを本質的に「乗算」して、より大きな遷移テーブルを作成していることがわかります。したがって、結果のテーブルから DFA を引き出すことができます。これは正しく聞こえますか?また、すべての DFA ケースで機能するはずですか?それとも何か不足していますか?

4

1 に答える 1

13

理解するための鍵は、2 つの DFA を同時に実行する必要があること、または一般にユニオン DFA で両方の DFA の状態を維持する必要があることです。

そのため、ユニオン DFA の新しい状態を、元の状態の直接乗算として作成する必要があります。このようにして、元の DFA の状態のすべての組み合わせの状態を取得できます。

その場合、新しい DFA の移行ルールを直接計算できます。たとえば、状態 Ab にあり、入力で 0 を取得した場合、最初の DFA は状態 B になり、2 番目の DFA は状態 b になるため、この入力に対する結合 DFA の次の状態は Bb になります。

この方法は、2 つ以上の DFA のユニオンを作成する必要がある場合に常に機能します。結果の DFA は最適ではないかもしれませんが、後で任意のアルゴリズムで最小化できます。

于 2010-12-15T12:56:50.823 に答える