Exámenes

POR INTUICIÓN CREO QUE ES VERDADERA PERO NO LOGRO ENTENDER LO DE "CORREN EN PARALELO" Ya que con corren en paralelo me imagino lo de que la misma tira para ser aceptada debe cumplir con los dos automatas pero lo que no entiendo es como se crearia un nuevo automata de pila a raiz de el de pila y el automata finito determinista, Y las "simulaciones de movimientos"

 i) Sean L1 libre de contexto y L2 regular, entonces L3 = L1 L2 es libre de contexto. VERDADERO. Se dará una idea de la construcción de un APD M3 / L3 = L(M3) aunque no la demostración formal de que ese autómata reconoce efectivamente L3. Sea M1 / L1 = L(M1) ; M1 = (QM , Σ, Γ, δM , q0 , Z0 , FM ) y sea M2 / L2 = L(M2) ; M2 = (QA , Σ, δA , p0 , FA ). Se construye un APD M3 / L3 = L(M3) que “corre en paralelo M1 y M2”. M3 simula movimientos en M1 con entrada epsilon sin cambiar el estado de M2. Cuando M3 hace un movimiento con entrada a, M1 simula el movimiento y también simula a M2 con cambios de estado con esa entrada a. M3 acepta si y sólo si ambos autómatas M1 y M2 aceptan. Formalmente, se define entonces M3 = (QA × QM , Σ, Γ, δ, [p0,q0], Z0 , FA × FM ) donde δ es definido por δ([p, q], a, X), contiene ([p', q'], γ) si y sólo si δA (p, a) = p' y δM (q, a, X) contiene (q', γ). Notar que a puede ser epsilon, en cuyo caso p' = p