Pré-requisito: Matemática Discreta para Computação, Computação I.
Carga horária: 60h.
EMENTA:
- Sistemas de Estados Finitos, Conceitos sobre Linguagens e Gramáticas.
- Hierarquia de Classes de Linguagens.
- Autômatos Finitos Determinísticos e Não Determinísticos.
- Linguagens Regulares.
- Linguagens Livres de Contexto.
- Máquina de Turing.
- Linguagens Sensíveis ao Contexto.
- Linguagens Recursivas.
- Tese de Church.
- Linguagens Recursivamente Enumeráveis.
- Problemas de Decisão.
BIBLIOGRAFIA BÁSICA:
1.Hopcroft, J. E.; Motwani, R.; Ullman, J. D. Introdução á Teoria de Autômatos, Linguagens e
Computação. 2a. ed., Rio de Janeiro: Elsevier, 2002.
2.Menezes, P. B. Linguagens Formais e Autômatos. 5a. ed., Porto Alegre: Instituto de Informática da
UFRGS: Sagra Luzzatto, 2005.
BIBLIOGRAFIA COMPLEMENTAR:
1.Ramos, M. V. M.; Neto, J. J.; Vega, I. S. Linguagens Formais – Teoria, Modelagem e Implementação.
Porto Alegre: Bookman, 2009.
2.Lewis, H. R.; Papadimitriou, C. H. Elementos de Teoria da Computação. 2a. ed., Rio de Janeiro:
Bookman, 2004.