LFA

       LINGUAGENS FORMAIS E AUTÔMATOS

        Prof. João Luís Garcia Rosa

2o. semestre de 2005

Centro de Ciências Exatas, Ambientais e de Tecnologias

PUC-Campinas
   Faculdade de Engenharia de Computação

CONFIRMADO: A PROVA SERÁ NO DIA 30/11!

Máquinas de Turing e Gramáticas

I. EMENTA

Estudo detalhado das linguagens formais. Relação entre autômatos e classes de linguagens. Problemas decidíveis e indecidíveis.

II. PROGRAMA

1. LINGUAGENS REGULARES E AUTÔMATOS FINITOS

1.1. A Primeira Linguagem

1.2. Gramáticas e Linguagens

1.3. Propriedades de Fechamento

1.4. Linguagens Regulares e de Estados Finitos

1.5. Exercícios

2. LINGUAGENS LIVRES DE CONTEXTO E AUTÔMATOS A PILHA

2.1. Linguagens Livres de Contexto

2.2. Programas, Linguagens e Parsing

2.3. Gramáticas Livres de Contexto e a Língua Natural

2.4. Formas Normais para Gramáticas Livres de Contexto

2.5. Autômatos a Pilha

2.6. O Teorema da Equivalência

2.7. Exercícios

3. LINGUAGENS SENSÍVEIS AO CONTEXTO E AUTÔMATOS LIMITADOS LINEARMENTE

3.1. Gramáticas e Linguagens Sensíveis ao Contexto

3.2. Máquinas de Turing

3.3. Autômatos Limitados Linearmente

4. LINGUAGENS DO TIPO 0 E MÁQUINAS DE TURING

4.1. A Máquina de Turing Universal

4.2. Máquinas de Turing Não Determinísticas

4.3. O Problema da Parada (Halting) e a Indecidibilidade

4.4. Técnicas para Construção de Máquinas de Turing

4.5. Exercícios

III. AVALIAÇÃO

2 provas:

P1 = 28/09 (quarta-feira)

P2 = 05/12 (segunda-feira)

2 provas substitutivas:

P3 = 05/10 (quarta-feira)

P4 = 12/12 (segunda-feira)

Trabalho em grupo: T

Entrega do Trabalho: 21, 23 e 28/11

Integridade Acadêmica:

A “cola” ou plágio em provas, exercícios ou atividades práticas implicará na atribuição de nota zero para todos os envolvidos. Dependendo da gravidade do incidente, o caso será levado ao conhecimento da Direção e do Conselho de Faculdade, para as providências cabíveis. Na dúvida do que é considerado cópia ou plágio, o aluno deve consultar o professor antes de entregar um trabalho.

Aulas:

Turma 1: Segundas e Quartas, das 9h55 às 11h35

Turma 2: Segundas e Quartas, das 12h55 às 14h35

Média Final = (P1 ou P3) * 0,4 + (P2 ou P4) * 0,4 + T * 0,2.

IV. BIBLIOGRAFIA

Hopcroft, J. E., Ullman, J. D., Motwani, R. Introdução à Teoria de Autômatos, Linguagens e Computação. 2a. Edição. Editora Campus, 2003.

Moll, R. N., Arbib, M. A., and Kfoury, A. J. (1988), An Introduction to Formal Language Theory, Springer-Verlag.

Hopcroft, J. E. and Ullman, J. D. (1969), Formal Languages and Their Relation to Automata, Addison-Wesley Publishing Company.

Floyd, R. W., and Beigel, R. (1994), The Language of Machines - An Introduction to Computability and Formal Languages, Computer Science Press.

Taylor, R. G. and Taylor, S. (1997), Models of Computation and Formal Languages, Oxford University Press. Deus Ex Machina

Simon, I. (1981), Linguagens Formais e Autômatos, Segunda Escola de Computação, IMECC-Unicamp.

Material disponível: