Linguagens Formais
Apresentação da Disciplina - 2011/2
Turno Noturno
Prof. Othon M. N. Batista
Mestre em Informática
Sumário







Ementa
Justificativa
Objetivos
Conteúdo
Metodologia
Datas e Pesos das Avaliações
Referências
Ementa









Introdução à teoria das linguagens;
hierarquia de Chomsky;
autômatos finitos e expressões regulares;
propriedades dos conjuntos regulares;
gramáticas livres de contexto;
autômatos com pilha;
máquinas de Turing;
decidibilidade e tratabilidade;
complexidade computacional.
Justificativa

Entendimento das linguagens
computacionais;

base para compiladores;

entendimento da teoria da computação.
Objetivos

Aprender:
– linguagens formais;
– geradores e reconhecedores;
– máquina universal;
– decidibilidade e tratabilidade;
– complexidade computacional.
Conteúdo

Primeira avaliação:
– introdução às linguagens formais;
– linguagens regulares:
• gramáticas regulares;
• autômatos finitos.
Conteúdo

Segunda avaliação:
– linguagens livres de contexto:
• gramáticas livres de contexto;
• autômatos com pilha.
– linguagens sensíveis ao contexto:
• gramáticas sensíveis ao contexto;
• máquinas de Turing.
Conteúdo

Terceira avaliação:
– teoria da computação:
• decidibilidade;
• tratabilidade;
• complexidade computacional.
Metodologia

Aulas expositivas;

listas de exercícios;

trabalhos.
Avaliações

Primeira avaliação: 13 de Setembro
– Prova = 2,0 & trabalho = 0,7

Segunda avaliação: 01 de Novembro
– Prova = 2,0 & trabalho = 0,7

Terceira avaliação: 06 de Dezembro
– Prova = 1,0 & trabalho = 0,6
Referências

MENEZES, P. B. Linguagens Formais e
Autômatos. 4a edição. Editora Sagra
Luzzato, 2000.

DIVÉRIO, T. A. e MENEZES, P. B. Teoria da
Computação - Máquinas Universais e
Computabilidade. 2a edição. Editora Sagra
Luzzato, 2000.