La longitud total de la entrada a un autómata pushdown que acepta mediante una pila vacía es un límite superior en los estados numéricos y los símbolos de la pila.

Question

Estaba repasando el texto clásico. "Introducción a la teoría, los lenguajes y la computación de los autómatas" (tercera edición) por Jeffrey Ullman, John Hopcroft, Rajeev Motwani, donde encontré algunas declaraciones sobre un autómata pushdown (PDA) que acepta por pila vacía, como:

1. $n$, la longitud total de la entrada, es seguramente un límite superior en el número de estados y símbolos de pila.

2.Una regla podría colocar casi n símbolos en la pila.

Las siguientes declaraciones se hicieron mientras los autores estaban a punto de tomar algunas notas sobre las propiedades de decisión de los CFL (lenguajes libres de contexto).

Ahora aquí hay algunos puntos por los cuales posiblemente pueda contradecir la afirmación en lugar de demostrar que es correcta.

1. Suponer $n$, es la longitud total de la entrada, pero según el diseño de la PDA podría suceder que para aceptar la cadena de entrada no estén involucrados todos los estados de la PDA, por lo que con esto no podemos decir que $n$ es un límite superior en el número de estados que tiene la PDA.

2. Aunque el PDA acepta por pila vacía, puede suceder que una función de transición agregue más de $n$ elementos en la parte superior de la pila, pero al final al consumir el $n$ Al ingresar símbolos, podemos permanecer en el estado particular y usar transiciones épsilon para permanecer en el mismo estado y sacar los elementos de la pila hasta que quede vacía.Entonces, ¿cómo podemos decir eso? $n$ ¿Existe un límite superior para los elementos numéricos de la pila?Llegamos a una contradicción...

No entiendo dónde estoy cometiendo el error, porque las mismas declaraciones están escritas en la tercera edición del libro sin que se hayan realizado cambios con respecto a la segunda edición, lo que hace probable que la declaración sea correcta.

Adjunto la parte correspondiente del texto a continuación:

Answer 1

Esa sección no habla de análisis.Los algoritmos a los que se hace referencia son algoritmos para convertir entre CFG y PDA de diferentes tipos.La pregunta es, como siempre, "¿cuál es la complejidad computacional del algoritmo?", y la respuesta, como siempre, se expresa en términos del tamaño de la entrada: al algoritmo.

La entrada a un algoritmo que convierte una PDA en un CFG es la PDA, y el tamaño de la entrada (la métrica para la complejidad del algoritmo) es el tamaño de la *PDA".Eso es lo que pretenden los autores. norte ser.

¿Cómo se mide el tamaño de una PDA?Simple:escribe el PDA como una cadena en algún lenguaje de definición de PDA y cuenta los símbolos en la descripción.Este es un procedimiento completamente justo, porque para llamar al algoritmo de conversión en la PDA, es necesario darle al convertidor una entrada que represente la PDA.

Dada esa definición, las afirmaciones no sorprenden en absoluto.Cada estado y cada símbolo del alfabeto deben estar presentes al menos una vez en la descripción de la PDA, por lo que el tamaño de esa descripción es un límite superior.De manera similar, es posible que la mayor parte de la descripción de la PDA sea la descripción de una sola regla, lo que podría empujar a casi n símbolos.