Как использовать конструкцию пересечения для формирования DFA?

Идея довольно проста, хотя я вижу, где возникает путаница. Я дам текстовое/символическое описание процесса создания машин пересечения (объединения, разности) с помощью конструкции декартовой машины произведения (то же самое, что вы говорите о).

ЦКА — это набор из 5 (E, Q, q0, A, f), где

1. E - входной алфавит, непустой конечный набор символов
2. Q - множество состояний, непустое и конечное.
3. q0 — начальное состояние, элемент Q
4. A - набор принимающих или конечных состояний, подмножество Q
5. f - функция перехода, берущая пары из Q x E в Q

Скажем, у нас есть две машины M' = (E', Q', q0', A', f') и M'' = (E'', Q'', q0'', A'', f'') . Для облегчения обсуждения предположим, что E' = E''. Теперь мы построим M''' так, чтобы L(M''') = L(M') пересекалось (или объединение, или разность) L(M'').

1. Возьмем Е''' = Е'' = Е'
2. Возьмем Q''' = Q' x Q''
3. Возьмем q0''' = (q0', q0'')
4. Возьмем A''' = (x, y), где x в A' и y в A'' (для объединения x в A' или y в A''; для разности x в A', но не y в A'). ').
5. Возьмем f'''((x, y), e) = (f'(x, e), f''(y, e)).

Ну вот! Давайте теперь рассмотрим две машины: одну, которая принимает a^2n, и другую, которая принимает a^3n (пересечение должно быть машиной, принимающей a^6n... правильно?).

Для М' имеем...

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

Для М'' имеем...

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

Для М''' мы получаем...

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).

И вот! Пожалуйста, дайте мне знать, если это нуждается в разъяснении.

Это: {s∈{a,b,c}∗: за каждым a в s сразу следует ab} {s∈{a,b,c}∗: за каждым a в s сразу следует ab} и {s ∈{a,b,c}∗: каждому c в s непосредственно предшествует ab}

Впереди еще и автомат, можно соединить состояния "0" и "2".

и вам нужно сохранить это ...

Существует точный способ выполнения автоматов для скрещивания языков. Пусть AA и BB — входные автоматы. Случаями нового автомата будут все пары состояний AA и BB, то есть SA∩B=SA×SBSA∩B=SA×SB, начальное состояние будет iA∩B=⟨iA,iB⟩iA∩B= ⟨iA,iB⟩, где iAiA и iBiB — начальные состояния AA и BB, а FA∩B=FA×FBFA∩B=FA×FB, где FXFX обозначает множество допускающих состояний XX. Наконец, функция перехода δA∩BδA∩B определяется следующим образом для любой буквы α∈Σα∈Σ и состояниях p1,p2∈SAp1,p2∈SA, q1,q2∈SBq1,q2∈SB:

⟨p1,q1⟩−→−−A∩B α ⟨p2,q2⟩ тогда и только тогда, когда p1−→A α p2andq1−→B α q2 ⟨p1,q1⟩→A∩B α ⟨p2,q2⟩ тогда и только тогда, когда p1→A α p2andq1→B α q2 Обратите внимание, что такой автомат обычно не является минимальным (например, пересечение может быть просто пустым языком). Кроме того, может быть полезно (но не обязательно) сделать входные автоматы минимальными, поскольку выходной размер квадратичен. // Ссылка: math.stackexchange.com Удачное кодирование...