Operações com linguagens livres de contexto e lema de pumping
7 Novembro 2018, 09:30 • André Souto
Operações com linguagens livres de contexto.
Qualquer linguagem regular é livre de contexto.
Reunião, concatenação e fecho de Kleene de linguagens livres de contexto são livres de contexto.
Intersecção de uma linguagem livre de contexto com uma regular é livre de contexto.
Lema de bombeamento para linguagens livres de contexto. Enunciado e esquisso da prova.
Exemplos de linguagens que não são livres de contexto.
Estudar secção 2.3 do Sipser.