Autômatos: Finitos, a Pilha e Máquina de Turing (linearmente limitada). Linguagens Formais: Regular, Livre e Sensível ao Contexto, Estrutura de Frases. Hierarquia de Chomsky. Aplicações em compiladores. Computabilidade: modelos computacionais (funções recursivas, linguagens de programação), funções não computáveis, problema da parada, decidibilidade.

diariocpl

• DIVERIO, T. A.; MENEZES, P. B. Teoria da Computação: máquinas universais e computabilidade. Porto Alegre: Sagra Luzzatto, 2004.

• LEWIS, H. R.; PAPADIMITRIOU, C. H. Elementos de Teoria da Computação. Porto Alegre: Bookman, 2000. 2ª ed.

• MENEZES, P. F. B. Linguagens Formais e Autômatos. Porto Alegre: Sagra Luzzatto, 2002. 4ª ed.