Esses slides de aula esboçam uma prova de que não pode ser aceito por nenhum Empurrão Determinístico Autômato. Infelizmente, os slides não fornecem referências sobre a origem da prova.
Fiquei me perguntando, alguém sabe de um artigo ou livro acadêmico que dê uma prova completa? Adoraria poder citá-lo, mas não consegui encontrar um.
Respostas:
O resultado é comprovado em Ginsburg e Greibach, linguagens livres de contexto determinístico , Inform. Controle 9 (6), 620–648, 1966 , Teorema 4.1 na página 24 (643). No entanto, a prova parece um pouco diferente.
fonte