Carga horária da disciplina: 4 horas/aula

Professor(es) em 2018-2

Turma 11

Professor: Rodrigo Geraldo Ribeiro - www | e-mail Horários: Segunda-feira (10h10 - 11h50) Quarta-feira (10h10 - 11h50)

Objetivos

Ao final do curso é esperado que os alunos compreendam as definições e propriedades de modelos matemáticos de computação: linguagens, autômatos e gramáticas. Também é esperado que os alunos compreendam a noção de decidibilidade de problemas e que tenham uma noção sobre como reconhecer problemas computacionalmente decidíveis e não decidíveis.

Ementa

Linguagens regulares, expressões regulares, autômatos de estados finitos; linguagens e gramáticas livres de contexto, autômatos de pilha; linguagens e gramáticas sensíveis ao contexto; máquinas de Turing, tese de Church-Turing; computabilidade e decidibilidade; hierarquia de Chomsky.

Conteúdo Programático

- Introdução: alfabetos, strings e linguagens
- Autômatos de Estados Finitos Deterministas e não Deterministas
- Expressões Regulares
- Minimização de Autômatos Finitos
- Propriedades de Linguagens Regulares
- Lema do Bombeamento para Linguagens Regulares (LRs)
- Gramáticas e Linguagens Livres de Contexto (LLC)
- Ambiguidade
- Propriedades de LLCs
- Autômatos de Pilha
- Forma normal de Chomsky
- Gramáticas Regulares e Gramáticas Sensíveis ao Contexto
- Lema do Bombeamento para LLCs
- Máquinas de Turing
- Tese de Church-Turing
- Problemas de Decisão
- Indecidibilidade do Problema da Parada
- Problemas decidíveis e não decidíveis sobre linguagens

Bibliografia

- VIEIRA, Newton José. Introdução aos fundamentos da computação: linguagens e máquinas. São Paulo: Thomson Pioneira, 2006.
- SIPSER, Michael. Introdução à teoria da computação. São Paulo. Thomson Learning, 2007.
- SUDKAMP, Thomas A. Languages and machines: an introduction to the theory of computer Science. 2 ed. Addison Wesley, 1997.

Bibliografia complementar

- LEWIS, Harry R.; PAPADIMITRIOU, Christos H. Elementos de teoria da computação. 2. ed. Porto Alegre: Bookman, 2000.
- DAVIS, Martin. Computability and unsolvability. New York: Dover, 1982.
- LEEUWEN, J. Van. Handbook theoretical computer science. Amsterdam: Elsevier Cambridge, Mass.: MIT., 1990.
- EPSTEIN, Richard L.; CARNIELLI, Walter A. Computability, computable functions, logic and the foundations of mathematics. Pacif. Grove: Wadsworth, 1989.
- MENDELSON, Elliott. Introduction to mathematical logic. 3. ed. Pacific Grove, CA: Wadsworth & Brooks / Cole Advanced Brooks & Software, 1987.