Propriedades das linguagens livres de contexto e lema de bombeamento para linguagens livres de contexto

3 Novembro 2020, 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 para o lema de bombeamento para linguagens livres de contexto.

Estudar a secção 2.2 do Sipser.

Aula em regime síncrono não presencial com transmissão via Zoom.