CCO - 410 - Aspectos formais da computação

Quantidade de créditos: 8
Total de horas de aulas teóricas: 60
Total de horas de aulas de exercícios, seminários ou estudos dirigidos : 60

Objetivo

Estudar as teorias relativas aos autômatos e às linguagens formais e as relações de equivalência envolvendo esses modelos. Aplicar essas teorias na modelagem e solução de problemas computacionais bem como identificar problemas indecidíveis.

Ementa

  • Seqüências, alfabetos, linguagens, grafos, árvores, conjuntos e relações.
  • Autômatos finitos e expressões regulares.
  • Gramáticas livres de contexto.
  • Máquinas de Turing
  • Indecidibilidade.
  • Linguagens livre de contexto determinísticas.
  • Complexidade computacional
  • Problemas intratáveis.

Bibliografia Principal

  1. Hopcroft, J.E., Motwani, R. and Ullman, J.D. - Introduction to Automata Theory, Languages, and Computation, Addison-Wesley, 3rd. edition,2007.
  2. Harrison, M.A., "Introduction to Formal Language Theory", Addison-Wesley, 1978.
  3. Hopcroft, J.E., Ulman, J.D., "Introduction to Formal Language Theory", Addison-Wesley, 1978.
  4. Linz, P. An Introduction to Formal Languages and Automata. Jones & Barlett Learning Book, 6th edition, 2017.
  5. Menezes, P.B. Linguagens Formais e Autômatos, Ed. Bookman, 6a.edição, 2010.