Ответ 1
Идея довольно проста, хотя я вижу, где возникает путаница. Я дам текстовое/символическое описание процесса создания машин пересечения (объединения, разности) через конструкцию Cartesian Product Machine (то же самое, что и вы говорите).
A DFA является 5-кортежем (E, Q, q0, A, f), где
- E - входной алфавит, непустой конечный набор символов
- Q - множество состояний, непустых и конечных
- q0 - начальное состояние, элемент Q
- A - это набор принимающих или конечных состояний, подмножество Q
- 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' ').
- Возьмем E '' '= E' '= E'
- Возьмем Q '' '= Q' x Q ''
- Возьмем q0 '' '= (q0', q0 '')
- Возьмем A '' '= (x, y), где x в A' и y из A '' (для объединения, x в 'или y из A' ', для разности x в A', но не y в '').
- Возьмем f '' '((x, y), e) = (f' (x, e), f '' (y, e)).
Иди сюда! Теперь рассмотрим две машины: одну, которая принимает a ^ 2n, и тот, который принимает a ^ 3n (пересечение должно быть машиной, принимающей a ^ 6n... right?).
Для M 'имеем...
- E '= {a}
- Q '= {s0, s1}
- q0 '= s0
- A '= {s0}
- f '(s0, a) = s1, f' (s1, a) = s0
Для M '' имеем...
- E '' = {a}
- Q '' = {t0, t1, t2}
- q0 '' = t0
- A '' = {t0}
- f '' (t0, a) = t1, f '' (t1, a) = t2, f '' (t2, a) = t0
Для M '' 'получаем...
- E '' '= {a}
- Q '' '= {(s0, t0), (s0, t1), (s0, t2), (s1, t0), (s1, t1), (s1, t2)}
- q0 '' '= (s0, t0)
- A '' '= {(s0, t0)} для пересечения, {(s0, t0), (s0, t1), (s0, t2), (s1, t0)} для объединения, {(s0, t1), (s0, t2)} для разности.
- 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).
И вот ты! Пожалуйста, дайте мне знать, если это потребует разъяснений.
