Equivalência entre PDA e CFG, propriedades das linguagens livres de contexto e lema de bombeamento para linguagens livres de contexto.

26 Outubro 2021, 09:30 • André Souto

Exemplo de como construir um PDA que reconhece uma linguagem dada por uma gramática livre de contexto.

Prova que toda a linguagem regular é reconhecível por um PDA. 

Exemplo.
Prova que o conjunto das linguagens livres de contexto é fechado para união, concatenação e fecho de Kleene.

Motivação, enunciado e prova do lema de bombeamento para linguagens livres de contexto.


Os alunos devem estudar a secção 2.2 do livro do Sipser.