Construir autómatas pushdown para idiomas dados

Requisito previo: autómatas pushdown , aceptación de autómatas pushdown por estado final 
Un autómata pushdown es similar a un autómata finito determinista excepto que tiene algunas propiedades más que un DFA. La estructura de datos utilizada para implementar un PDA es stack. Una PDA tiene una salida asociada con cada entrada. Todas las entradas se colocan en una pila o simplemente se ignoran. El usuario puede realizar las operaciones básicas de inserción y extracción en la pila que se utiliza para PDA. Uno de los problemas asociados con los DFA era que no podía contar la cantidad de caracteres que se ingresaban en la máquina. PDA evita este problema ya que utiliza una pila que también nos proporciona esta facilidad. 

Un Autómata Pushdown (PDA) se puede definir como – 
M = (Q, Σ, Γ, δ, q0, Ζ, F) donde  

• Q es un conjunto finito de estados
• Σ es un conjunto finito que se llama el alfabeto de entrada
• Γ es un conjunto finito que se llama el alfabeto de pila
• δ es un subconjunto finito de QX ( Σ ∪ {ε} X Γ XQX Γ ^* ) la relación de transición.
• q ₀ ∈ Q es el estado inicial
• Ζ ∈ Γ es el símbolo de pila inicial
• F ⊆ Q es el conjunto de estados de aceptación

Representación del Estado de Transición – 

Representación de Push en una PDA –

Representación del Pop en una PDA – 

Representación de Ignorar en una PDA – 

P) Construya un PDA para el lenguaje L = {0 ⁿ 1 ^m 2 ^m 3 ⁿ | n>=1, m>=1}

Enfoque utilizado en este PDA: 
los primeros 0 se colocan en la pila. Luego, los 1 se colocan en la pila. 
Luego, por cada 2 como entrada, se saca un 1 de la pila. Si aún quedan algunos 2 y la parte superior de la pila es un 0, la PDA no acepta la string. A partir de entonces, si los 2 están terminados y la parte superior de la pila es un 0, entonces por cada 3 como entrada se saca de la pila un número igual de 0. Si la string está terminada y la pila está vacía, la PDA acepta la string; de lo contrario, no la acepta.

• Paso 1: al recibir 0, empújelo a la pila. Al recibir 1, empújelo a la pila y vaya al siguiente estado
• Paso 2: Al recibir 1 empújelo a la pila. Al recibir 2, saque 1 de la pila y vaya al siguiente estado
• Paso 3: al recibir 2 pop 1 de la pila. Si todos los 1 se han sacado de la pila y ahora recibe 3, saque un 0 de la pila y vaya al siguiente estado
• Paso 4: al recibir 3 pop 0 de la pila. Si la entrada finaliza y la pila está vacía, vaya al último estado y se acepta la string

Ejemplos: 

Input  : 0 0 1 1 1 2 2 2 3 3
Result : ACCEPTED

Input  : 0 0 0 1 1 2 2 2 3 3 
Result : NOT ACCEPTED 

P) Construya un PDA para el lenguaje L = {0 ⁿ 1 ^m | norte >= 1, metro >= 1, metro > n+2}

Enfoque utilizado en este PDA: 
los primeros 0 se colocan en la pila. Cuando se terminan los 0, se ignoran dos 1. A partir de entonces, por cada 1 como entrada, se saca un 0 de la pila. Cuando la pila está vacía y aún quedan algunos 1, se ignoran todos. 

• Paso 1: al recibir 0, empújelo a la pila. Al recibir 1, ignórelo y vaya al siguiente estado
• Paso 2: al recibir 1, ignórelo y vaya al siguiente estado
• Paso 3: al recibir 1, extraiga un 0 de la parte superior de la pila y vaya al siguiente estado
• Paso 4: al recibir 1, saque un 0 de la parte superior de la pila. Si la pila está vacía, al recibir 1 ignórelo y vaya al siguiente estado
• Paso 5: Al recibir 1 ignóralo. Si la entrada ha terminado, vaya al último estado

Ejemplos: 

Input  : 0 0 0 1 1 1 1 1 1
Result : ACCEPTED

Input  : 0 0 0 0 1 1 1 1
Result : NOT ACCEPTED