Aceptación de autómatas pushdown por estado final

Hemos discutido Pushdown Automata (PDA) y su aceptación por el artículo de pila vacía. Ahora, en este artículo, discutiremos cómo la PDA puede aceptar una CFL según el estado final. Dado un PDA P como:

P = (Q, Σ, Γ, δ, q0, Z, F)

El lenguaje aceptado por P es el conjunto de todas las strings que consumen y que la PDA puede pasar del estado inicial al estado final, independientemente de cualquier símbolo que quede en la pila, que se puede representar como:

L(P) = {w |(q0, w, Z) =>(qf, ɛ, s)}

Aquí, desde el estado inicial q0 y el símbolo de pila Z, se alcanza el estado final qf ɛ F cuando se consume la entrada w. La pila puede contener una string s que es irrelevante ya que se alcanza el estado final y se aceptará w. 

Ejemplo: Definir los autómatas pushdown para lenguaje {a^nb^n | n > 0} usando el estado final. 

Solución: M = donde Q = {q0, q1, q2, q3} y ∑ = {a, b} y Γ = { A, Z } y F={q3} y δ está dada por:

δ( q0, a, Z ) = { ( q1, AZ ) }
δ( q1, a, A) = { ( q1, AA ) }
δ( q1, b, A) = { ( q2, ɛ) }
δ( q2, b, A) = { ( q2, ɛ) }
δ( q2, ɛ, Z) = { ( q3, Z) }

Veamos cómo funciona este autómata para aaabbb: 

Explicación: Inicialmente, el estado de los autómatas es q0 y el símbolo en la pila es Z y la entrada es aaabbb como se muestra en la fila 0. Al leer a (mostrado en negrita en la fila 1), el estado cambiará a q1 y empuje el símbolo A en la pila. En el próximo a (que se muestra en la fila 2), empujará otro símbolo A en la pila y permanecerá en el estado q1. Después de leer 3 a, la pila será AAAZ con A en la parte superior. Después de leer b (como se muestra en la fila 4), aparecerá A y se moverá al estado q2 y la pila será AAZ. Cuando se lean todas las b, el estado será q2 y la pila será Z. En la fila 7, en el símbolo de entrada ɛ y Z en la pila, se moverá a q3. Como se ha alcanzado el estado final q3 después de procesar la entrada, se aceptará la string. Este tipo de aceptación se conoce como aceptación por el estado final.. A continuación, veremos cómo funciona este autómata para aab:

  

Como podemos ver en la fila 4, la entrada ha sido procesada y el PDA está en el estado q2, que es un estado no final, la string aab no será aceptada. Discutamos la pregunta basándonos en esto: 

Que-1. Considere el diagrama de transición de un PDA que se muestra a continuación con el alfabeto de entrada ∑ = {a, b} y el alfabeto de pila Γ = {X, Z}. Z es el símbolo de pila inicial. Sea L el idioma aceptado por la PDA. (GATE-CS-2016) 

Solución: Primero etiquetamos el estado de la PDA dada como:

  

A continuación, el PDA P dado se puede escribir como:

 Q = {q0, q1, q2} and ∑ = {a, b} 
And Γ = {X, Z} and F={q0,q2} and δ is given by :
δ( q0, a, Z ) = {( q0, XZ)}
δ( q0, a, X) = {( q0, XX )}
δ( q0, b, X) = {( q1, ɛ)}
δ( q1, b, X) = {( q1, ɛ)}
δ( q1, ɛ, Z) = {( q2, Z)}

Como podemos ver, q0 es el estado tanto inicial como final, se aceptará ɛ. Por cada a, X se coloca en la pila y el PDA permanece en el estado final. Por lo tanto, cualquier número de a puede ser aceptado por PDA. Si la entrada contiene b, se extrae X de la pila para cada b. Luego, el PDA se mueve al estado final si la pila se vacía después de procesar la entrada (δ( q1, ɛ, Z) = {( q2, Z)}). Por lo tanto, un número de b debe ser igual al número de an si existen. Como solo hay un movimiento para un estado y una entrada determinados, el PDA es determinista. Entonces, la opción correcta es (D).