Diferencia entre NPDA y DPDA

Un Pushdown Automata (PDA) es una forma de implementar la gramática libre de contexto de manera similar. Diseñamos Autómatas Finitos para Gramática Regular.

1. Es más potente que FSM.
2. FSM tiene memoria muy limitada pero PDA tiene más memoria.
3. PDA= Máquina de estados finitos + Pila

Esta pila tiene memoria infinita y eso facilita la mayor potencia de los autómatas Pushdown . Esto ayuda a que la PDA se comporte de forma más potente que la máquina de estados finitos .

Un autómata pushdown tiene tres componentes:

1. Una cinta de entrada
2. Una unidad de control finita.
3. Una pila de tamaño infinito.

Definición de DPDA y NPDA con ejemplo

Sea M = (Q,∑,Γ,q0, Z,F ,δ) un PDA. El PDA es determinista si y solo si

1. δ(q, a, Z) tiene un elemento.
2. Si δ(q, a, Z) no está vacío, entonces δ(q0, a, Z) debería estar vacío.

Ambas condiciones deben cumplirse para que el PDA sea determinista. Si una de las condiciones falla, el PDA no es determinista.

Consideremos un ejemplo para entender más claramente.

Ejemplo: ¿La PDA corresponde al idioma L = {a ⁿ b ⁿ | n>=1} por el estado finito es determinista?

Solución: Las transiciones mostradas definidas para esta máquina se muestran a continuación:

δ(q0, a,  Z0) =δ(q0, aZ0) 
δ(q0, a,  a) =δ(q0, aa) 
δ(q0, b,  a) =δ(q1, ∈) 
δ(q1, b,  a) =δ(q1, ∈)  
δ(q1, ∈,  Z0) =δ(qf, ∈) 

El PDA debe satisfacer las dos condiciones. mostrado en la definición como determinista.

1. δ(q ₀ , a, Z ₀ ) tiene un solo elemento. En este caso, para cada q∈Q, a∈∑ y Z∈Γ, solo existe una definición, por lo que se cumple la primera condición.
2. Para satisfacer la segunda condición considere la transición. δ(q ₁ ,∈ , Z ₀ ) = (q _f ,∈ _, ). Dado que la transición está definida, la transición δ(q, a, Z ₀ ) donde a∈∑ no debe definirse, lo cual es cierto.

ya que ambas condiciones. están satisfechos, entonces el PDA dado es determinista.

Diferencia entre NPDA y DPDA:

S. No	DPDA (autómatas pushdown deterministas)	NDPA (autómatas pushdown no deterministas)
1.	Es menos potente que NPDA.	Es más potente que DPDA.
2.	Es posible convertir cada DPDA a un NPDA correspondiente.	No es posible convertir cada NPDA a un DPDA correspondiente.
3.	El lenguaje aceptado por DPDA es un subconjunto del lenguaje aceptado por NDPA.	El lenguaje aceptado por NPDA no es un subconjunto del lenguaje aceptado por DPDA.
4.	El lenguaje aceptado por DPDA se llama DCFL (Lenguaje libre de contexto determinista) que es un subconjunto de NCFL (Lenguaje libre de contexto no determinista) aceptado por NPDA.	El lenguaje aceptado por NPDA se llama NCFL (Lenguaje libre de contexto no determinista).

Hay una diferencia más de la siguiente manera:
 

DPDA: Por cada entrada con el estado actual, solo hay un movimiento.

            M = (Q,∑,Γ,q0, Z,F,δ)

            δ: Q*∑*Γ→Q*Γ

NPDA: Para cada entrada con el estado actual, podemos tener múltiples movimientos.

            M = (Q,∑,Γ,q0, Z,F,δ)

            δ: Q*{∑∪∈}*Γ→2 ^Q *Γ ^*

¿Por qué NPDA es más poderoso que DPDA?

NDPA es más poderoso que DPDA porque podemos agregarle más transiciones. Es posible que cada idioma agregue una transición. Para algunos lenguajes, podemos construir DPDA, existe un NPDA pero hay algunos lenguajes que son aceptados por NPDA pero no por DPDA. Se dice que esto es poderoso cuando acepta más conjuntos de lenguajes que otros autómatas. 

De hecho, es más poderoso que DFA (autómatas finitos deterministas) y NFA (autómatas finitos no deterministas) también porque, en el caso de DFA y NFA, son equivalentes en poder. Entonces, para cada idioma aceptado por DFA, existe un NFA y viceversa. No hay ningún idioma para el que construimos NFA pero no DFA. Por lo tanto, no podemos convertir NPDA a DPDA siempre y podemos convertir NFA a DFA equivalente siempre.