PUERTA | Puerta TI 2005 | Pregunta 38

Sea P un autómata push-down no determinista (NPDA) con exactamente un estado, q, y exactamente un símbolo, Z, en su alfabeto de pila. El estado q es tanto el estado inicial como el estado de aceptación del PDA. La pila se inicializa con una Z antes del inicio de la operación de la PDA. Sea Σ el alfabeto de entrada de la PDA. Sea L(P) el lenguaje aceptado por la PDA al leer una string y alcanzar su estado de aceptación. Sea N(P) el lenguaje aceptado por la PDA al leer una string y vaciar su pila.
¿Cuál de las siguientes afirmaciones es verdadera?

 
(A) L(P) es necesariamente Σ* pero N(P) no es necesariamente Σ*
(B) N(P) es necesariamente Σ* pero L(P) no es necesariamente Σ*
(C) Ambos L(P) y N(P) son necesariamente Σ*
(D) Ni L(P) ni N(P) son necesariamente Σ*

Respuesta: (D)
Explicación: El lenguaje L(P) aceptado por Push Down Automata (PDA) al leer string y alcanzando
su estado de aceptación y el idioma N(P) aceptado por la PDA al leer
una string y vaciar una pila, pero puede darse el caso de que la string tenga
una configuración muerta sobre las transiciones de la PDA, es decir, la PDA no tiene
una transición para un alfabeto o string en particular. Por eso no acepta
todas las strings sobre Σ*.

For example- Transitions for the PDA are as follows:
1. (q, a, Z) -> (q, aZ)
2. (q, b, Z) -> (q, bZ)
3. (q, a, a) -> (q, aa)
4. (q, a, b) -> (q, ab)
5. (q, b, a) -> (q, ba)
6. (q, null, Z) -> (q, Z)
7. (q, null ,a) -> (q, null)
8. (q, null, b) -> (q, null)

Aquí q es el estado inicial y de aceptación, Z es el símbolo de pila inicial
y a y b son los alfabetos de entrada. Aquí {null, a, b, ab, aab………..} se
aceptan en ambos casos, pero en caso de “bb”, la PDA entra en una
configuración inactiva ya que no existe tal transición. Por tanto, ni L(P) ni N(P)
son necesariamente Σ*.

Esta explicación ha sido aportada por Yashika Arora.
Cuestionario de esta pregunta