¿Existe un autómata universal de empuje?

Question

Dejemos que $\Sigma$ sea un alfabeto fijo y que $PDA(\Sigma)$ es el conjunto de todos los autómatas push down (PDA) que tienen el alfabeto de entrada $\Sigma$ . ¿Existe un alfabeto $S$ y una función $f:PDA(\Sigma) \to S^$ tal que el conjunto $\{(f(A),w) : w \in L(A)\}$ es aceptada por un autómata push-down no determinista? Si no es así, ¿la respuesta es positiva si sustituimos los PDA por autómatas finitos (manteniendo el reconocedor universal como PDA)?

Answer 1

Esto no es posible, suponiendo que $(f(A),w)$ significa escribir el código de $A$ y luego escribir la entrada $w$ . Los lenguajes libres de contexto (y regulares) tienen una propiedad de bombeo, es decir, ciertas subcadenas pueden repetirse. Supongo que has visto el concepto. Los límites de longitud de las partes repetidas están determinados por el lenguaje que te interesa, y pueden ser arbitrariamente grandes. La "PDA universal", por otro lado, tiene su propia constante de bombeo fija que no puede coincidir con valores grandes arbitrarios en los lenguajes codificados. Sin embargo, este argumento sólo funciona si podemos imponer que se evite el bombeo en el $f(A)$ parte de la descripción. Para los lenguajes regulares eso no es un gran problema, para los libres de contexto necesitamos un resultado de bombeo bastante fuerte.

Lo siento, no hay detalles aquí. No hay suficiente espacio ....