Aceptación de Pushdown Automata

Hay dos formas diferentes de definir la aceptabilidad de PDA.

Aceptabilidad final del estado

En la aceptabilidad del estado final, una PDA acepta una cadena cuando, después de leer la cadena completa, la PDA está en un estado final. Desde el estado inicial, podemos hacer movimientos que terminen en un estado final con cualquier valor de pila. Los valores de la pila son irrelevantes siempre que terminemos en un estado final.

Para un PDA (Q, ∑, S, δ, q 0 , I, F), el lenguaje aceptado por el conjunto de estados finales F es -

L (PDA) = {w | (q 0 , w, I) ⊢ * (q, ε, x), q ∈ F}

para cualquier cadena de pila de entrada x.

Aceptabilidad de pila vacía

Aquí una PDA acepta una cadena cuando, después de leer la cadena completa, la PDA ha vaciado su pila.

Para un PDA (Q, ∑, S, δ, q 0 , I, F), el lenguaje aceptado por la pila vacía es -

L (PDA) = {w | (q 0 , w, I) ⊢ * (q, ε, ε), q ∈ Q}

Ejemplo

Construya una PDA que acepte L = {0n 1n | n ≥ 0}

Solución

Este idioma acepta L = {ε, 01, 0011, 000111, .............................}

Aquí, en este ejemplo, el número de ‘a’ y ‘b’ tiene que ser el mismo.

  • Inicialmente ponemos un símbolo especial ‘$’ en la pila vacía.

  • Entonces en el estado q2, si encontramos la entrada 0 y top es Null, empujamos 0 a la pila. Esto puede repetirse. Y si encontramos la entrada 1 y la parte superior es 0, sacamos este 0.

  • Entonces en el estado q3, si encontramos la entrada 1 y la parte superior es 0, sacamos este 0. Esto también puede iterar. Y si encontramos la entrada 1 y top es 0, sacamos el elemento superior.

  • Si el símbolo especial '$' se encuentra en la parte superior de la pila, se abre y finalmente pasa al estado de aceptación q 4 .

Ejemplo

Construya una PDA que acepte L = {ww R | w = (a + b) *}

Solution

Inicialmente colocamos un símbolo especial '$' en la pila vacía. En el estadoq2, la wse está leyendo. En el estadoq3, cada 0 o 1 aparece cuando coincide con la entrada. Si se proporciona cualquier otra entrada, la PDA pasará a un estado inactivo. Cuando llegamos a ese símbolo especial '$', vamos al estado de aceptaciónq4.