Как использовать конструкцию пересечения для формирования 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

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

1. Взять E '' '= E' '= E'
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)).

Вот, пожалуйста! Теперь давайте рассмотрим две машины: одну, которая принимает ^ 2n, и другую, которая принимает ^ 3n (пересечение должно быть машиной, принимающей ^ 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).

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

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