Papier avec preuve que

8

Ces diapositives de cours esquissent une preuve queL={anbn∣n≥0}∪{anb2n∣n≥0} ne peut être accepté par aucun automate déterministe à refoulement. Malheureusement, les diapositives ne donnent aucune référence quant à l'origine de la preuve.

Je me demandais, quelqu'un connaît-il un document ou un manuel universitaire qui en donne une preuve complète? J'adorerais pouvoir le citer, mais je n'ai pas pu en trouver un.

formal-languages reference-request automata pushdown-automata nondeterminism jmite
la source
Remarque: les diapositives suivent le même argument que celui que j'utilise dans une question connexe sur le lemme de pompage pour les LFC déterministes. (Il s'agit bien sûr d'un argument sans pompage.)
Hendrik Jan

Réponses:

6

Le résultat est prouvé dans Ginsburg et Greibach, Langages libres de contexte déterministe , Inform. Control 9 (6), 620–648, 1966 , Theorem 4.1 à la page 24 (643). Cependant, la preuve semble quelque peu différente.

Yuval Filmus
la source
Impressionnant! Merci beaucoup! J'avais vu des références à ce document, mais j'avais du mal à trouver une copie PDF.
jmite
1
Par curiosité, comment avez-vous trouvé cela? Saviez-vous simplement par hasard dans quel papier il se trouvait, ou l'avez-vous cherché d'une manière ou d'une autre? J'essaie de développer mes capacités de recherche de papier ...
jmite
1
J'ai googlé «sans contexte déterministe» et c'était l'un des meilleurs résultats. Le résumé ne semblait pas trop prometteur, mais dans l'introduction, ils mentionnent ce résultat.
Yuval Filmus