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.
JOHNSONBAUGH, R. Discrete Mathematics, Prentice-Hall Inc., 1997, ISBN: 0-13-518242-5. LEWIS, H.R.; PAPADIMITRIOU, C.H. Elements of the theory of computation, Prentice-Hall Inc., 1981, ISBN: 0-13-273417-6. HARRISON, M.A. Introduction to formal language theory, Addison-Wesley, 1978. HOPCROFT; ULLMAN, J.D. Introduction to formal languages and automata theory, Addison-Wesley, 1976.
