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.
Linguagens formais e autômatos. Conceitos básicos de computabilidade e complexidade.
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.
Livros texto: SIPSER, M. Introdução à Teoria da Computação Ed. Cengage Learning, 2005 Bibliografia complementar: • CARNIELLI, W. e EPSTEIN, R. Computabilidade, funções computáveis, lógica e os fundamentos da matemática. Ed. UNESP, 2009 • LEWIS, H. R.; PAPADIMITRIOU, C. H.. Elementos de Teoria da Computação. Ed. Bookman, 2000. 2 ed. • NEWTON, J. V. Introdução à Teoria da Computação: Linguagens e Máquinas, São Paulo: Pioneira Thomson Learning, 2006. • RAMOS, M. V. M.; NETO, J. J.; VEGA, I. S. Linguagens Formais: Teoria, Modelagem e Implementação. Ed. Bookman, 2009.