Of.: S-6 T:04 L:00 HS:04 SL:04 C:04

Pre-Req.: MC538 AA200

Ementa:

Revisão de conceitos básicos; alfabetos e linguagens; linguagens regulares; linguagens livres de contexto; linguagens recursivas e linguagens recursivamente enumeráveis; computabilidade e decidibilidade.

Programa:

1. Revisão de conceitos básicos: indução, relações e fecho de relações
2. Alfabetos e linguagens
3. Linguagens Regulares
1. Gramáticas lineares à direita e à esquerda
2. Autômatos finitos
3. Não determinismo
4. Minimização de autômatos finitos
5. Equivalência de modelos
6. Teorema da iteração
7. Propriedades de linguagens regulares
4. Linguagens livre de contexto
1. Gramáticas livres de contexto
2. Derivações e árvores de derivação
3. Ambiguidade
4. Formas normais para gramáticas livres de contexto
5. Autômatos a pilha
6. Equivalência de modelos
7. Teorema da iteração
8. Propriedades de linguagens livre de contexto
5. Linguagens recursivas e linguagens recursivamente enumeráveis
1. Máquinas de Turing
2. Restrições e extensões para máquinas de Turing
3. Linguagens recursivas e recursivamente enumeráveis
4. Máquina universal
5. Grámáticas sensíveis ao contexto e grámáticas irrestritas
6. Hierárquia de Chomsky
7. Equivalência de modelos

 

 

6. Computabilidade e Decidibilidade
1. Problemas de decisão
2. Problemas decidíveis, parcialmente decidíveis e indecidíveis
3. Problema da parada em máquinas de Turing
4. Reduções
5. Problema da correspondência de Post
6. Problemas indecidíveis e linguagens livre de contexto

Bibliografia:

D. Kelly. Automata and Formal Languages. Prentice-Hall, 1995

J. E. Hopcroft e J. D. Ullman. Introduction to Automata Theory, Languages and Computation. Addison-Wesley, 1979

R. W. Floyd e R. Beigel. The Language of Machines. W.H. Freeman, 1994

M. Minsky. Computation: Finite and Infinite Machines. Prentice-Hall, 1967

M. A. Harrison. Introduction to Formal Language Theory. Addison-Wesley, 1978