CCO - 410 - Formal Aspects of Computing

Amount of credits: 8
Total hours of theoretical classes: 60
Total hours of exercise classes, seminars or directed studies): 60

Objective

To study theories related to automata and formal languages and the equivalence relations involving these models. To apply these theories in modeling and solving problems as well as identify undecidable problems.

Catalog Description

  • 1 - Sequences, alphabets, languages, graphs, trees, sets and relations
  • 2 - Finite automata and regular expressions
  • 3 - Context free grammars
  • 4 - Turing Machines
  • 5 - Undecidability
  • 6 - Deterministic context-free languages
  • 7 - Computational complexity
  • 8 - Intractable problems

Main Bibliography

  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.