PUERTA | GATE-IT-2004 | Pregunta 40

¿Cuál de las siguientes strings no es miembro de L (M)?

 
(A) aaa
(B) aabab
(C) baaba
(D) bab

Respuesta: (C)
Explicación:  
Conceptos básicos de PDA
Un autómata de empuje hacia abajo o PDA es esencialmente un NFA con una pila y su función de transición también depende del símbolo en la parte superior de la pila. Formalmente, una PDA es una tupla de 6 (Q, Σ, Γ, δ, q0, F) siendo Q el conjunto de todos los estados posibles, Σ es el conjunto de todas las entradas posibles, Γ es el conjunto de todos los símbolos de pila posibles, δ : Q × Σ × Γ → Q × Γ es la función de transición, q0 es el estado inicial y
F ⊆ Q es el conjunto del estado final.

Algunas veces, también se sabe que PDA tiene 7 tuplas cuando consideramos el símbolo de pila inicial z0 como un miembro adicional en las
6 tuplas anteriores. Tenga en cuenta que debería existir una función de transición para una entrada determinada; de lo contrario, no habrá ningún movimiento posible.

El PDA puede ser de dos tipos: PDA de aceptación de pila vacía y PDA de estado final.

Los PDA que aceptan pila vacía son los PDA para los que se acepta una entrada dada si en una string de entrada dada, cuando la entrada se agota, la pila debería estar vacía.

De manera similar, un PDA que acepta el estado final es un PDA para el cual se acepta una entrada dada si en una string de entrada dada, cuando la entrada se agota, el PDA debería estar en uno de los estados finales.

Un PDA no determinista o NPDA es un PDA en el que, para una entrada dada, es posible una salida múltiple. es decir, la función de transición δ asigna una entrada dada de Q × Σ × Γ a un conjunto finito de Q × Γ.

Para la pregunta dada , dado que hay más de una salida correspondiente a una entrada dada para la función de transición, consideraremos un NPDA para la ejecución de la entrada y detendremos nuestra ejecución para una rama correspondiente si no hay movimiento posible para una entrada dada y Suponemos que si la máquina se detiene en uno de los estados finales y la entrada se agota, aceptamos la string; de lo contrario, la rechazamos. Tenga en cuenta que el PDA dado es el estado final que acepta el PDA y no la pila vacía que acepta el PDA.

Elección de las preguntas:
 

Supondremos que el símbolo de pila inicial es ε, y
 

• En la opción 1 , la ejecución será de la siguiente manera:
(s, a, ) → (s, a) o (f, ε).
Primero consideremos (s, a) como salida y ejecutemos la entrada restante. (s,a, a) → Ningún movimiento válido. detener esta rama y no en el estado final, por lo que no se acepta. Ahora considere (f, ε) como salida. (f, a, ε) → Sin movimiento válido.
detener esta rama Observe que la PDA está en uno de los estados finales, pero la string de entrada no está agotada, por lo que la PDA no debería aceptarla.
 
• En la opción 2 , la ejecución comenzará a partir de la opción 1 y se detendrá en el personaje 2 como ningún movimiento posible. Esta opción tampoco se acepta de la misma forma que la primera opción.
3
 

• En la opción 3 , la ejecución será la siguiente:
(s, b, ε) → (s, a). (s, a, a) → No hay movimiento posible. detener esta rama . Ya que se detuvo antes de llegar a cualquier estado final por lo que no se acepta esta opción.
 

• En la opción 4 , esta opción tampoco se acepta ya que la PDA se detendrá en el segundo carácter como se detuvo en la opción anterior. Esta opción tampoco se acepta.
 

Suponiendo que si la PDA se detiene en una entrada debido a que no hay movimiento posible y si el estado actual es uno de los estados finales pero la entrada no está agotada, la PDA rechazará esa string. Para la pregunta 2, todas las respuestas son verdaderas, es decir, ninguna de las dada para la string pertenece al idioma de la PDA dada.

Nuevamente, suponiendo que si la PDA se detiene en una entrada debido a que no hay movimiento posible y si el estado actual es uno de los estados finales pero la entrada no está agotada, la PDA seguirá consumiendo la string de entrada hasta que llegue el final de la string, La string en la opción (A) y la opción (B) será aceptada por el lenguaje de esta PDA. mientras que la opción (C) y la opción (D) aún no serán aceptadas ya que al final
de la string, el PDA no estará en el estado final. Entonces, teniendo en cuenta esta suposición, la opción (C) y la opción (D) serán ciertas para esta pregunta.

Esta explicación es aportada por Durgesh Pandey.
Cuestionario de esta pregunta