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.

Gramáticas Livres do Contexto

25 Outubro 2021, 08:00 • Paulo Jorge Cunha Vaz Dias Urbano

Exercícios sobre Gramáticas Livres do Contexto.

Resolução de exercícios da 3ª folha

22 Outubro 2021, 11:30 • André Souto

Resolução de exercícios da 3ª folha sobre lema de bombeamento para linguagens regulares. 

Resolução de exercícios da 3ª folha

22 Outubro 2021, 08:00 • André Souto

Resolução de exercícios da 3ª folha sobre lema de bombeamento para linguagens regulares. 

Lema do Bombeamento

22 Outubro 2021, 08:00 • Paulo Jorge Cunha Vaz Dias Urbano

Exercícios sobre o Lema de Bombeamento para as Linguagens Regulares