Construir autómatas pushdown para L = {a^nba^2n | norte ≥ 0}

requisitos previos:

• Introducción de autómatas pushdown
• Construir autómatas pushdown para idiomas dados

Problema – Construir PDA para el lenguaje L = {a ⁿ ba ²ⁿ | norte ≥ 0} . 

Esto significa que la PDA debería tener el doble de a después de b que antes de b, y debería haber una y sólo una b.

Ejemplos:

INPUT : aaabaaaaaa
OUTPUT : Accepted

INPUT : aaaaabaaaa
OUTPUT : Rejected

INPUT : NULL STRING
OUTPUT : Rejected 

Acercarse:

Presione el doble de a por cada a que recibamos como símbolo de entrada. Seguimos repitiendo esto hasta que recibimos b. Una vez, el símbolo de entrada es b, omita b y extraiga una a para cada a.

NOTA: Para cada pregunta de este tipo, cuando el número de un determinado símbolo es un múltiplo de otro símbolo, la clave es hacer que la cuenta de ambos símbolos sea igual.

1. <STATE q0 > At empty stack if we get 'a' as input symbol, push 2 a's to the stack.
2. If we get 'b' as input symbol we move to q1.
3. <STATE q1 > For every a that we get as input symbol now, we pop 1 a.
4. If end of string symbol is encountered then transit to q2.

Los autómatas pushdown requeridos: