2つのDFAの結合をどのように構成しますか？

Question

誰かが与えられた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 

我々は2 DFAのオーバー{0,1}を持っていると言う：

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

私は私の講義ノートの絵ソリューションを持って、どのように他の人がそれを記述するかを見たいと思っています。これから、私は本質的にこれら2つの元のテーブルを状態値を使って「掛け合わせて」、より大きな遷移テーブルを得ることがわかります。このようにして、得られたテーブルからDFAを引き出すことができる。これは正しいと思いますが、これはすべてのDFAケースで機能するのでしょうか、それとも欠けているものがありますか？

Answer 1

2つのDFAを同時に実行する必要があるか、または一般的にDFAの両方のDFAの状態を維持する必要があることを理解することが重要です。

あなたは元の状態の直接の乗算として組合DFAのための新しい状態を作成する必要が理由です。このようにして、元のDFAの各状態の組み合わせごとに状態があります。

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

この方法は、2つ以上のDFAの結合を作成する必要がある場合はいつでも機能します。結果として得られるDFAは最適ではないかもしれませんが、後であなたが好きなアルゴリズムで最小化することができます。