finite automata - resueltos - ¿Cómo usar la construcción de la intersección para formar un DFA?

hallar la expresion regular de un automata

Question

Estoy haciendo una tarea para mi clase de teoría de computación y estoy un poco confundido sobre cómo combinar 2 DFA. El libro dice que usa la "construcción de intersección" para hacerlo, pero no estoy seguro de qué es eso. Aquí hay 2 ejemplos:

Answer 1

Estos son: {s∈ {a, b, c} ∗: cada a in s es seguido inmediatamente por ab} {s∈ {a, b, c} ∗: cada a in s es seguido inmediatamente por ab} y {s ∈ {a, b, c} ∗: cada c en s está inmediatamente precedido por ab}

En frente y otro autómata, puedes unir estados "0" y "2".

y necesitas retener eso ...

Existe una forma precisa de realizar autómatas para el cruce de idiomas. Sean AA y BB los autómatas de entrada. Los casos de autómatas nuevos serán todos los pares de estados de AA y BB, es decir, SA∩B = SA × SBSA∩B = SA × SB, el estado inicial será iA∩B = ⟨iA, iB⟩iA∩B = ⟨IA, iB⟩, donde iAiA e iBiB son los estados iniciales de AA y BB, y FA∩B = FA × FBFA∩B = FA × FB donde FXFX denota el conjunto de estados de aceptación de XX. Por último, la función de transición δA∩BδA∩B se define de la siguiente manera para cualquier letra α∈Σα∈Σ y establece p1, p2∈SAp1, p2∈SA, q1, q2∈SBq1, q2∈SB:

⟨P1, q1⟩− → −−A∩B α ⟨p2, q2⟩ iff p1− → A α p2andq1− → B ​​α q2 ⟨p1, q1⟩ → A∩B α ⟨p2, q2⟩ iff p1 → A α p2andq1 → B α q2 Tenga en cuenta que, por lo general, este autómata no es mínimo (por ejemplo, la intersección podría ser solo un idioma vacío). Además, podría ser útil (pero no es necesario) hacer que los autómatas de entrada sean mínimos, ya que la salida es de tamaño cuadrático. // Referencia: math.stackexchange.com Happy Coding ...

Answer 2

La idea es bastante clara, aunque puedo ver dónde entra la confusión. Daré una descripción textual / simbólica del proceso para hacer las máquinas de intersección (unión, diferencia) a través de la construcción de la Máquina de Producto Cartesiana (lo mismo que usted está hablando) acerca de).

Un DFA es un 5-tuple (E, Q, q0, A, f) donde

1. E es el alfabeto de entrada, un conjunto finito de símbolos no vacío
2. Q es el conjunto de estados, no vacíos y finitos.
3. q0 es el estado de inicio, un elemento de Q
4. A es el conjunto de estados finales o de aceptación, un subconjunto de Q
5. f es la función de transición, tomando pares de Q x E a Q

Digamos que tenemos dos máquinas M ''= (E'', Q '', q0'', A '', f'') y M '''' = (E '''', Q '''', q0 '''', A '''', f '''') . Para facilitar la discusión, asumimos que E ''= E'' ''. Ahora construiremos M '''' ''de modo que L (M'' '''') = L (M '') se cruce (o unión o diferencia) L (M'' '').

1. Toma E '''' ''= E'' ''= E''
2. Toma Q '''' ''= Q'' x Q ''''
3. Tome q0 '''' ''= (q0'', q0 '''')
4. Tome A '''' ''= (x, y) donde x en A'' e y en A '''' (para unión, x en A ''o y en A'' ''; para la diferencia, x en A'' pero no y en A '' '').
5. Tome f '''' ''((x, y), e) = (f'' (x, e), f '''' (y, e)).

¡Ahí tienes! Consideremos ahora dos máquinas: una que acepta a ^ 2n, y otra que acepta a ^ 3n (la intersección debe ser una máquina que acepta a ^ 6n ... ¿verdad?).

Para M '', tenemos ...

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

Para M '''', tenemos ...

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

Para M '''' '', obtenemos ...

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)} para la intersección, {(s0, t0), (s0, t1), (s0, t2), (s1, t0)} para la unión, {(s0, t1), (s0, t2)} por diferencia.
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).

¡Y ahí tienes! Por favor, hágamelo saber si esto necesita una aclaración.