Fornecer ao aluno noção formal de algoritmo, computabilidade e do problema de decisão. Apresentar ferramentas que auxiliem na solução de problemas com o auxílio do computador. Habilitar o aluno na tarefa de definir linguagens de programação (sua sintaxe e semântica), por meio dos conceitos relativos às gramáticas formais.
Linguagens Regulares: Autômatos finitos, expressões, propriedades e técnicas descritivas. Linguagens Livres de Contexto: Gramáticas, derivações, ambigüidade. Linguagens Dependentes de Contexto: Máquinas de Turing, definições básicas. Indecibilidade: Máquinas de Turing Universais. Teoria de Complexidade.
Linguagens Regulares: Autômatos finitos determinísticos e não-determinísticos; expressões regulares; propriedades e técnicas para identificar e descrever linguagens regulares. Linguagens Livres de Contexto: Gramáticas Livres de Contexto; derivações; árvores de derivação; ambigüidade; autômatos a pilha. Linguagens Dependentes de Contexto e Linguagens com Estrutura de Frase: Máquinas de Turing; definições básicas e sua relação com a noção de um algoritmo/programa. Indecibilidade: Máquinas de Turing Universais; Problemas indecidíveis. Teoria de Complexidade: Complexidade de Tempo, Complexidade de Espaço, Intratabilidade.
1. SIPSER, M. Introduction to the Theory of Computation. PWS, 2a ed, 1997.2. HOPCROFT, M. & ULLMAN Introduction to Automata Theory, Languages, and Computation. Addison-Wesley, 2001.3. HAREL, D. Algorithmics – The Spirit of Computing. Addison-Wesley, 2. ed., 1992.4. DIVÉRIO & MENEZES Teoria da Computação – Máquinas Universais e Computabilidade. Série Livros Didáticos 5, IF UFRGS, 2. ed., 2000, Sagra Luzzatto.5. MENEZES, P.B. Linguagens Formais e Autômatos, Série Livros Didáticos 3, IF UFRGS, 4. ed., 2001, Sagra Luzzatto.6. TOSCANI & VELOSO Complexidade de Algoritmos, Série Livros Didáticos 13, IF UFRGS, 1. ed., 2001, Sagra Luzzatto.
