Papel con prueba de que

8

Estas diapositivas de la conferencia bosquejan una prueba de queL={unanortesinorte∣norte≥0 0}∪{unanortesi2norte∣norte≥0 0} no puede ser aceptado por ningún autómata determinista pushdown. Desafortunadamente, las diapositivas no dan referencias de dónde proviene la prueba.

Me preguntaba, ¿alguien sabe de un trabajo académico o libro de texto que da una prueba completa? Me encantaría poder citarlo, pero no he podido encontrar uno.

formal-languages reference-request automata pushdown-automata nondeterminism jmite
fuente
Como nota: las diapositivas siguen el mismo argumento que el que uso en una pregunta relacionada sobre Pumping Lemma's para CFL determinista. (Este es un argumento que no bombea, por supuesto).
Hendrik,

Respuestas:

6

El resultado se demuestra en Ginsburg y Greibach, Lenguajes deterministas sin contexto , Inform. Control 9 (6), 620–648, 1966 , Teorema 4.1 en la página 24 (643). Sin embargo, la prueba se ve algo diferente.

Yuval Filmus
fuente
¡Increíble! Muchas gracias! Había visto referencias a ese documento, pero tuve problemas para encontrar una copia en PDF.
jmite
1
Por curiosidad, ¿cómo encontraste eso? ¿Sabía de antemano en qué papel estaba, o lo buscó de alguna manera? Estoy tratando de desarrollar mis habilidades de búsqueda de papel ...
jmite
1
Busqué en Google "libre de contexto determinista" y fue uno de los mejores resultados. El resumen no parecía demasiado prometedor, pero en la introducción mencionan este resultado.
Yuval Filmus