00.LFA.apresentação 2014-3

Prévia do material em texto

LINGUAGENS FORMAIS 
E AUTÔMATOS
2o sem./2014
Professor: Itamar Leite de Oliveira
itamar.leite@ufjf.edu.br
DCC063
 Total de Créditos: 4
 Turma: A
 Pré-requisitos: DCC013- Estrutura de Dados.
 Teste de Verificação de Conhecimento: 3
 Média: 60.0
 Prova de segunda chamada/substitutiva para
aqueles que não fizeram um dos TVC’s.
 Frequência: haverá chamada (?).
Informações Gerais
Informações Gerais
Dias da’s aulas:
18/12: último dia de aulas
 1ª 2ª 3ª 4ª 5ª 
Lin
g. F
orm
ais 
e A
utô
ma
tos
 Agosto Terça 19 26 
Sexta 22 29 
Setembro Terça 02 09 16 23 30 
Sexta 05 12 19 26 
Outubro Terça 07 21 
Sexta 03 10 17 24 31 
Novembro Terça 04 11 18 25 
Sexta 07 14 21 28 
Dezembro Terça 02 09 
Sexta 05 12 
 
 Datas TVCs:
 TVC1: 23/09 (terça)
 TVC2: 04/11 (terça)
 TVC3: 02/12 (terça)
 Segunda chamada: 09/12 (terça) (reposição do
TVC1 ou TVC2 ou TVC3).
 Horário de Atendimento:
 terça, 17:00-19:00
Informações Gerais
 Metodologia
 Aulas expositivas (datashow + quadro)
 Exercícios resolvidos em sala
 Listas de exercícios
 Notas de aulas (PDF) no site:
 https://sites.google.com/a/ice.ufjf.br/lfaufjf/
 Livro: Ver bibliografia
Informações Gerais
1. Noções preliminares
Teoria de conjuntos. Produto cartesiano, relações
entre conjuntos, funções, relações de equivalência.
Conjuntos enumeráveis e não enumeráveis.
Definições recursivas. Indução matemática e
diagonalização. Tipos de formalismos: grafos
direcionados e lambda-cálculo.
Conteúdo:
2. Linguagens regulares
Definição de strings e linguagens. Especificação
finita de linguagens. Conjuntos e expressões
regulares
Conteúdo:
3. Gramáticas e linguagens livres de contexto
Definições de linguagens livres de contexto.
Derivação. Gramáticas regulares. Exemplos de
gramáticas e linguagens: Pascal e expressões
aritméticas. Estratégias de derivação: ambigüidade,
derivações mais à esquerda e mais à direita, grafos
de gramáticas, derivadores top-down, derivadores
bottom-up
Conteúdo:
4. Formas normais
Definição de formas normais e esquemas de
restrição em gramáticas. Eliminação de: produções
lambda, produções em cadeia, símbolos
redundantes, recursão à esquerda. Forma normal
de Chomsky e de Greibach
Conteúdo:
5. Autômatos e linguagens
Máquinas de estados finitos. Autômato finito
determinístico e não-determinístico. Remoção de
não-determinismo: fecho lambda. Minimização de
autômatos finitos determinísticos. Autômatos
finitos e conjuntos regulares. O lema do
bombeamento para linguagens regulares.
Conteúdo:
6. Autômatos com pilha e linguagens livres de
contexto
Definições de autômato com pilha. Autômatos com
pilha e linguagens livres de contexto. O lema do
bombeamento para linguagens livres de contexto.
Autômato com duas pilhas.
Conteúdo:
7. Hierarquia de Chomsky: classes de linguagens
Propriedades fechadas de linguagens regulares.
Propriedades fechadas de linguagens livres de
contexto. Tópicos para a próxima disciplina: Teoria
de Linguagens.
Conteúdo:
 Capacitar o aluno para a aplicação formal
sistematizada de conceitos e resultados relativos às
linguagens, gramáticas, autômatos e reconhecedores,
introduzindo modelos matemáticos de computação.
Especificamente, pretende-se que, após cursar esta
disciplina, o aluno deve:
- conhecer alfabetos e linguagens e saber representar de forma
finita objetos infinitos;
- conhecer gramáticas e linguagens (regulares, livre de contexto
e sensível ao contexto);
- ser capaz de entender e construir autômatos de pilha e finitos.
Objetivo
Bibliografia Básica
MENEZES, P. B. Linguagens formais e autômatos. Porto 
Alegre: Sagra Luzzatto. 2000. 170 p. (Livros didáticos)
LEWIS, H. R.; PAPADIMITRIOU, C. H. Elementos de teoria 
da computação. Porto Alegre: Bookman. 2000. 354 p.
Bibliografia Complementar
HOPCROFT, J. E. Introdução a teoria de autômatos, 
linguagens e computação. Rio de Janeiro: Elsevier. 560 p.
Bibliografia
Bibliografia Complementar
HOPCROFT, J. E.; ULLMAN, J. D. Formal languages and 
their relation to automata. Menlo Park: Addison-Wesley. 
1969. 250 p.
RAMOS, M. V. M.; NETO, J. J.; VEGA, Í. S. Linguagens 
formais: Teoria, modelagem e implementação. Porto 
Alegre: Bookman. 2009. 656 p.
SIPSER, M. Introdução à teoria da computação: 
Thomson Learning. 2007. 488 p.
AHO, A. V.; LAM, M. S.; SETHI, R. Compiladores: 
Princípios, técnicas e ferramentas Rio de Janeiro: 
Pearson. 2007. 648 p.
Bibliografia