finite-automata - 交差構造を使用して DFA を形成する方法は?

Question

計算理論クラスの宿題をしていて、2 つの DFA を組み合わせる方法が少しわかりません。そのために「交差構造」を使っていると本には書いてありますが、それが何なのかはわかりません。以下に 2 つの例を示します。

Answer 1

アイデアは非常に単純ですが、どこで混乱が生じるかはわかります。デカルト積マシンの構築 (あなたが話しているのと同じこと) を介して交差 (和、差) マシンを作成するプロセスをテキスト/記号で説明します。約）。

DFA は 5 タプル (E、Q、q0、A、f) であり、ここで

1. E は入力アルファベットであり、空でない有限のシンボル セットです。
2. Q は状態の集合であり、空ではなく、有限です
3. q0 は Q の要素である開始状態です
4. A は、受け入れ状態または最終状態のセットであり、Q のサブセットです
5. f は Q x E から Q までのペアを取る遷移関数です。

2 つのマシン M' = (E', Q', q0', A', f') と M'' = (E'', Q'', q0'', A'', f'') があるとします。 . 議論を簡単にするために、E' = E'' と仮定します。ここで、L(M''') = L(M') が L(M'') と交差 (または和集合または差) するように M''' を作成します。

1. E''' = E'' = E' を取る
2. Q''' = Q' x Q'' を取る
3. q0''' = (q0', q0'') を取る
4. A''' = (x, y) ここで、A' の x と A'' の y (結合の場合、A' の x または A'' の y; 差の場合、A' の x であり、A' の y ではありません) ')。
5. f'''((x, y), e) = (f'(x, e), f''(y, e)) を取ります。

ほら！a^2n を受け入れるマシンと a^3n を受け入れるマシンの 2 つのマシンを考えてみましょう (交差点は a^6n を受け入れるマシンである必要があります... ですよね?)。

M' については...

1. E' = {a}
2. Q' = {s0, s1}
3. q0' = s0
4. A' = {s0}
5. f'(s0, a) = s1, f'(s1, a) = s0

M'' については...

1. E'' = {a}
2. Q'' = {t0、t1、t2}
3. q0'' = t0
4. A'' = {t0}
5. f''(t0、a) = t1、f''(t1、a) = t2、f''(t2、a) = t0

M''' については...

1. E''' = {a}
2. Q''' = {(s0, t0), (s0, t1), (s0, t2), (s1, t0), (s1, t1), (s1, t2)}
3. q0''' = (s0, t0)
4. A''' = {(s0, t0)} (交差の場合)、{(s0, t0)、(s0、t1)、(s0、t2)、(s1、t0)} (和の場合)、{(s0, t1)、 (s0, t2)} の差。
5. f'''((s0, t0), a) = (s1, t1), f'''((s1, t1), a) = (s0, t2), f'''((s0, t2) 、a) = (s1、t0)、f'''((s1、t0)、a) = (s0、t1)、f'''((s0、t1)、a) = (s1、t2)、 f'''((s1, t2), a) = (s0, t0).

そして、そこに行きます！これについて説明が必要な場合はお知らせください。