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:

Textos disponíveis em formato PDF:

0. Apresentação

1. LINGUAGENS REGULARES E AUTÔMATOS FINITOS

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

    Resolução Exercício 15 - Forma Normal de Greibach

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

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

 

Listas de Exercícios:

Lista 1

Lista 2

Lista 3

Lista 4

 

Cópias dos slides em PDF (traduzidos e adaptados de R. Gregory Taylor):

1. Linguagens Regulares e Autômatos de Estados Finitos

2. Linguagens Livres de Contexto e Autômatos a Pilha (Push-Down)

3. O Conceito de Máquina de Turing (Descrição Informal)

4. Linguagens Sensíveis ao Contexto e Autômatos Limitados Linearmente

5. Variedades Adicionais das Máquinas de Turing

6. Os Limites da Computabilidade

 

VIRTUAL TURING MACHINE

 


Atualização: 07/11/2005