Exemplos de linguagens não regulares e introdução às linguagens livres de contexto.
13 Outubro 2021, 09:30 • André Souto
Recapitulação do lema de bombeamento.
Exemplos de linguagens não regulares e prova (usando o lema de pumping por contradição) para mostrar que elas não são regulares.
A hierarquia de Chomsky e posicionamento dos tipos de linguagens na hierarquia.
Périplo para a definição de gramáticas livres de contexto derivado das linguagens naturais, formação de gramáticas, noção de variáveis, símbolos terminais, regras de derivação.
Os alunos deve estudar as secções 1.4 e 2.1 do livro do Sipser.