Autómatas finitos compuestos (FA)

Requisito previo: autómatas finitos (FA)
El compuesto FA es el DFA resultante que se forma después de realizar la operación (∪, ∩, -) en los DFA dados D1 y D2.

D1 = (Q1, ∑, δ, q1, F1) and D2 = (Q2, ∑, δ, q2, F2) 

Donde,
Q ₁ y Q ₂ : Conjunto de estados finitos de DFA D1 y D2 respectivamente.
∑: El alfabeto de entrada contiene un número finito de símbolos de entrada.
δ: Función de transición (δ:Qx∑->Q)
q ₁ yq ₂ : Estado inicial de D1 y D2 respectivamente.
F ₁ y F ₂ : Conjunto de estados finales de DFA D1 y D2 respectivamente.

Propiedades de los autómatas finitos compuestos (FA):

1. El número de estados en el compuesto FA (D1XD2) es igual a m*n, donde m es el número de estados en D1 y n es el número de estados D2.
2. El estado inicial del compuesto FA es una combinación de los estados iniciales de D1 y D2.
3. El estado final del compuesto FA depende de la operación realizada.

Ejemplo:

D1 = no. of a's divisible by 2
D2 = no. of b's divisible by 3

D1 ({q1, B}, {a, b}, δ, q1, {q1}), 
D1 ({q2, A, C}, {a, b}, δ, q2, {q2}) 

Construya el FA mínimo para:

(D1∪D2), 
(D1∩D2), 
(D1-D2),
(D2-D1) 

Explicación:

DFA D1:

DFA D2:

1. Unión (D1∪D2):
cualquier string w que pertenezca al lenguaje de D1 o al lenguaje de D2 es aceptada por los autómatas compuestos resultantes.
Estado final : Si el estado final de D1 o el estado final de D2 contienen en cualquiera de los estados del compuesto FA.

2. Intersección (D1∩D2):
cualquier string w que pertenezca tanto al lenguaje de D1 como al lenguaje de D2 es aceptada por los autómatas compuestos resultantes.
Estado final : Si tanto el estado final de D1 como el estado final de D2 contienen en cualquiera de los estados del compuesto FA.

3. Diferencia (D1 – D2):
cualquier string w que sea aceptada por D1, no por D2.
Estado final : Si el estado final de D1 y el estado no final de D2 contienen en cualquiera de los estados del compuesto FA.

4. Diferencia (D2 – D1):
Cualquier string w que sea aceptada por D2, no por D1.
Estado final : Si el estado final de D2 y el estado no final de D1 contienen en cualquiera de los estados del compuesto FA.