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

Ответ 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).

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

Ответ 2

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

Впереди и в другом автомате вы можете присоединиться к состояниям "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⟩ iff p1- → A α p2 и q1- → B α q2 ⟨p1, q1⟩ → A∩B α ⟨p2, q2⟩ iff p1 → A α p2 и q1 → B α q2 Обратите внимание, что такой автомат обычно не минимален (например, пересечение может быть просто пустым языком). Кроме того, может быть полезно (но не обязательно) делать минимальные входные автоматы, так как выход квадратичен по размеру. // Ссылка: math.stackexchange.com Счастливое кодирование...