Apresentar uma introdução aos fundamentos matemáticos da Ciência da Computação, com ênfase em linguagens, reconhecedores (autômatos) e geradores (gramáticas). Enfatiza-se o estudo de dois tipos de questões no nível teórico: (I) Quais computações podem ser feitas em um computador? (II) Quão eficientemente podem ser realizadas?
Elementos de linguagens formais, cadeias, alfabetos, linguagens, gramáticas e reconhecedores. Hierarquia de Chomsky. Expressões regulares, autômatos finitos. Autômatos de pilha, Gramáticas livres de contexto. Relação entre autômatos e linguagens. Máquinas de Turing. Computabilidade. Complexidade computacional. Decidibilidade. Aplicações dos elementos da teoria à Engenharia de Computação.
1. Revisão de matemática discreta. 2. Linguagens, cadeias, alfabetos, conjuntos regulares. 3. Hierarquia de Chomsky. Expressões regulares. 4. Autômatos de estados finitos. 5. Autômatos de pilha. 6. Gramáticas livres de contexto. 7. Máquinas de Turing. Computabilidade. 8. Decidibilidade. 9. Aplicações à Engenharia de Computação.
1. HOPCROFT; ULLMAN, J.D. Introduction to formal languages and automata theory, Addison-Wesley,1976. 2. LEWIS, H.R.; PAPADIMITRIOU, C.H. Elements of the theory of computation, Prentice-Hall Inc., 1981, ISBN: 0-13-273417-6. 3. JOHNSONBAUGH, R. Discrete Mathematics, Prentice-Hall Inc., 1997, ISBN: 0-13-518242-5. 4. HARRISON, M.A. Introduction to formal language theory, Addison-Wesley, 1978. 5. SIPSER, M. Introdução à Teoria da Computação, 2a ed. norte-americana, Editora Thomson Pioneira, 2007. 6. RAMOS, M.V.M.; JOSÉ NETO, J.; VEGA, I.S. Linguagens Formais, Bookman, 2009.