Nesta aula, apresento a 3a parte da Seção 2.1 do Livro de Michael Sipser, "Introdução à Teoria da Computação". Mais especificamente, apresento a definição da Forma Normal de Chomsky (FNC) e o método de conversão de gramáticas livres-do-contexto para a FNC.
Autômatos Finitos e Linguagens Regulares: sistemas de estados finitos, autômatos finitos, linguagens regulares, expressões regulares, gramáticas regulares. Autômatos de Pilha e Linguagens Livres de Contexto: autômatos com pilha, linguagens livres de contexto, gramáticas livres de contexto e hierarquia de Chomsky. Conceitos básicos das teorias da computabilidade e da complexidade: Máquinas de Turing, problema da parada, decidibilidade, as classes de problemas P e NP e NP-completude.
Introduzir os conceitos de linguagens formais e autômatos e suas relações com linguagens de programação. Introduzir os conceitos básicos de computabilidade e complexidade, discutindo as limitações da ciência da computação.