NOTICE: This page is no longer mantained. Please check the new home page.

Material de Aula - Teoria da Computação

Notas de Aula

• Automatos Finitos
• Expressões Regulares
• Gramáticas e Linguagens Livres de Contexto

Exercícios

• 1ª lista - Autômatos Finitos
• 2ª lista - Autômatos Finitos Não-Determinísticos
• 3ª lista - Autômatos Finitos com Epsílon-transições
• 4ª lista - Expressões Regulares
• 5ª lista - Autômatos Finitos e Expressões Regulares
• 6ª lista - Gramáticas Livres de Contexto
• 7ª lista - Árvores de Análise Sintática, Aplicações de GLC e ambigüidade
• 8ª lista - Autômatos de Pilha
• 9ª lista - Formas Normais para Gramáticas Livres de Contexto
• 10ª lista - Máquinas de Turing

Trabalhos:

• Trabalho opcional sobre Problemas Indecidíveis e Problemas Intratáveis

Notas Finais

Links:

• Teoria da Computação no Wikipedia
• Máquina de Turing na Wikipedia
• Linguagens Formais e Automatos (Prof. Luiz A. M. Palazzo - UCPEL)
• Linguagens e Máquinas / Linguagens Formais e Automatos (Prof. Fernando Náufel - PUC/RIO)
• Linguagens Formais (Prof. S. Coutinho - UFRJ)
• Teoria da Computação e Linguagens Formais (Profª. Carla Alessandra Lima Reis e Prof. Eloi Favero - UFPA)
• Aspectos Formais da Computação (Prof. Sérgio Donizetti Zorzo - UFSCar)

Bibliografia:

• Hopcroft, J. E., Ullman, J. D., Motwani, R., Introdução à Teoria de Autômatos, Linguagens e Computação. Ed. Campus.
• Lewis, H. R., Papadimitriou, C. H., Elementos de Teoria da Computação. 2ª edição. Bookman.
• Menezes, P. B., Linguagens Formais e Automatos, Ed. Sagra Luzzatto.
• Diverio, T. A., Menezes, P. B., Teoria da Computação - Máquinas Universais e Computabilidade, Ed. Sagra Luzzatto