AFN Y AFD EJERCICIOS DE UNION E INTERSECCION

Uniones, intersecciones y complementos
de
Lenguajes Regulares
Sean M1 = (Σ, Q1, f1, q1, F1) y M2 = (Σ, Q2, f2, q2, F2), tales que L1 = L(M1)
y L2 = L(M2)

se define M = (Σ, Q, f, q0, F), donde definimos

Q = Q 1 x Q2
q0 = (q1,q2)
f((p,q),a) = (f1(p,a), f2(q,a)) = (t, r) donde p,t  Q1, q,r  Q2, a  Σ

Determinación de F:
Entonces:

1) L1  L2 = { (t,r) / t F1 ó r  F2 }
2) L1 ∩ L2 = { (t,r) / t F1 y r  F2 }
3) L1 – L2 = { (t,r) / t F1 y r  F2 }

Ejemplo unión L(M1) unión L(M2)

M = (Σ, Q, f, q0, F)

Q = { (A,P), (A ,T), (A,R), (B,P), (B, T), (B, R), (C,P), (C,T), (C,R)}

f ((A,P), 0) = (f1(A,0), f2(P,0)) = (B, T)
f ((A,T), 0) = (f1(A,0), f2(T,0)) = (B, T)
f ((A,R), 0) = (f1(A,0), f2(R,0)) = (B, T)
f ((B,P), 0) = (f1(B,0), f2(P,0)) = (C, T)
f ((B,T), 0) = (f1(B,0), f2(T,0)) = (C, T)
f ((B,R), 0) = (f1(B,0), f2(R,0)) = (C, T)
f ((C,P), 0) = (f1(C,0), f2(P,0)) = (C, T)
f ((C,T), 0) = (f1(C,0), f2(T,0)) = (C, T)
f ((C,R), 0) = (f1(C,0), f2(R,0)) = (C, T)