Pregunta sobre la pila de operación de la notación en la PDA

Question

Actualmente estoy leyendo dos libros:

1. Una Introducción a los Lenguajes Formales y Autómatas, 4ta Edición por Peter Linz.
2. Introducción a la Teoría de la Computación, 2a Edición por Michael Sipser.

Lo que me confunde es el notaciones utilizadas en estos dos libros son muy diferentes el uno del otro. Por ejemplo,

Deje $L = \{a^nb^{2n} : n \geq 0\}$

La solución a esta PDA es sencillo:

• Si leemos un $a$, pulsar dos marcadores (o conjunto de símbolos) en la pila.
• Si leemos un $b$, pop un marcador (o pila el símbolo de la pila.

Ahora, vamos a dibujar el real PDA:

1. Pedro Linz de la solución:
2. Michael Sipser la solución:

Hay varias diferencias que he notado:

• Con Pedro Linz de la pila del mecanismo, se puede realmente empujar 2 símbolos en la pila en un momento como contraposición a Michael Sipser, sólo podemos empujar 1 símbolo en la pila en un momento.
• Pedro Linz de la solución también se lleva a la parte superior de la pila en cuenta cada vez que se realiza un empujón. Por ejemplo, la transición de la $q_0$$q_1$: $$a, z \rightarrow 11z$$ $$a, 1 \rightarrow 111$$ Aquí, el PDA empuja dos 1's en una pila cada vez que se lee un $a$, pero también se ve en qué símbolo se encuentra en la parte superior de la pila. La cadena de $11z$ por ejemplo, significa que la parte superior $\rightarrow$ inferior y se lee de izquierda a derecha. Mientras Michael Sipser la solución no se preocupan realmente de la parte superior de la pila de símbolo. Mientras lee un $a$, empuja una $x$ en la pila. Más específicamente, la notación $$a, b \rightarrow c$$ significa
• leer una, si $a = \lambda$, lea nada.
• pop b, si $b = \lambda$, pop nada.
• pulse c, si $c = \lambda$, empujar nada.

Yo, personalmente, prefiero a Michael Sipser la notación más de Pedro Linz uno, porque creo que no es necesario mantener un seguimiento de qué símbolo se encuentra actualmente en la pila. A menos que exista un caso cuando este paso adicional asuntos, de lo contrario creo que es bastante trivial para expresar la transición de la función de Michael Sipser. Además, me pregunto si "es correcto" para permitir que empujar "2" símbolos en una época en la pila? Además, entre estos dos métodos, que uno es más estándar y más ampliamente utilizado?

Actualización Correcto PDA de Pedro Linz de la solución:

Answer 1

Yo creo que el principal moral aquí debe ser no importa.

Los dos métodos son evidentemente equivalente - empujando a cualquier número finito de símbolos de una sola vez puede lograrse mediante el uso de un conjunto finito de dedicación de los estados. En general cuando se habla de modelos de computación uno no debe perderse en los detalles específicos de la implementación como de largo ya que no hay gran diferencia entre ellos (por ejemplo, para una diferencia: el número de estados en un NDFA para un idioma puede ser exponencialmente más pequeño que el número de estados en el mejor de DFA para el idioma).

Cuando se llega a la teoría de la computabilidad vas a ver que esta "libertad de los detalles de implementación específica" es verdaderamente esencial si se quiere mantener el foco en lo importante.

Esta no es una característica de la ciencia computacional teórica solamente, por supuesto, a muchos de matemáticas libros sobre diversos temas, utilizar la notación que pueden ser muy diferentes el uno del otro. No hay ninguna regla universal de lo que es correcto; usted debe elegir la notación que más te guste y se adhieren a ella.