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.