Universidade Católica de Pelotas
Escola de Informática
Bacharelado em Ciência da Computação
Linguagens Formais e Autômatos
Prof. Luiz Antônio Moro Palazzo
LFA 2011.1
Pelotas, fevereiro de 2011
Roteiro
• Dados Gerais
• Objetivos
• Ementa
• Programa
• Bibliografia
• Avaliação
• Datas Importantes
• Recursos
Linguagens Formais e Autômatos - A01
2
Dados Gerais
•
•
•
•
•
•
Código:
Nome:
CH Total:
CH Semanal:
Pré-Requisitos:
É Pré-Requisito de:
364018
Linguagens Formais e Autômatos
60 horas-aula
(3-0-0)
estruturas Discretas II
Compiladores, Teoria da Computação
Linguagens Formais e Autômatos - A01
3
Objetivos
•
Apresentar os principais métodos
de tratamento sintático de
linguagens lineares abstratas,
com a respectiva associação às
linguagens típicas da ciência da
computação.
•
Estudar formalismos
operacionais, axiomáticos e
denotacionais e sua aplicação em
compiladores, interpretadores e
em ciência da computação em
geral.
Linguagens Formais e Autômatos - A01
4
Ementa
• Estudo das linguagens
formais, sua hierarquia e
representação. Estudo dos
autômatos finitos, seu
emprego como modelos
discretos e sua aplicação em
ciência da computação.
Linguagens Formais e Autômatos - A01
N
5
Programa
•
•
•
•
•
•
Modelagem e Representação.
Gramáticas.
Linguagens Regulares.
Autômatos Finitos.
Expressões Regulares.
Autômatos com Saída
• Primeira Avaliação.
•
•
•
•
•
Linguagens Livres de Contexto.
Autômatos com Pilha.
Linguagens Sensíveis ao Contexto.
Máquinas de Turing.
Introdução à Compilação.
• Segunda Avaliação.
Linguagens Formais e Autômatos - A01
6
Bibliografia
•
MENEZES, Paulo F B: Linguagens Formais e
Autômatos. P. Alegre: Sagra Luzzatto, 2004 (4a.ed).
•
HOPCROFT, J. E.; MOTWANI, R.; ULLMAN, J.D.:
Introduction to Automata Theory, Languages,
and Computation. New York: Addison-Wesley, 2004
(2a.ed).
•
LEWIS, H. R.; PAPPADIMITRIOU, C. H.: Elements of
the Theory of Computation. Englewood Cliffs:
Prentice-Hall, 1981.
•
SHIELDS, M. W.: An Introduction to Automata
Theory. Oxford: Blackwell Scientific Publications, 1987.
•
SALOMA, A.: Formal Languages. New York: Academic
Press, 1973.
Linguagens Formais e Autômatos - A01
7
Avaliação
• Duas provas: P1 e P2.
• Dois trabalhos: T1 e T2.
• N1=(6P1+4T1)/10.
• N2=(6P2+4T2)/10.
• A nota final do semestre
é a média aritmética
entre N1 e N2.
Linguagens Formais e Autômatos - A01
8
Datas Importantes
Prova 1 20 de abril
Entrega do Trabalho 1 27 de abril
Prova 2 22 de junho
Entrega do Trabalho 2 29 de junho
Avaliação Complementar 01 de julho
.
Linguagens Formais e Autômatos - A01
9
Recursos
• Página da disciplina:
http://infocat.ucpel.tche.br/disc/lfa/
• Lista de discussão:
Linguagens Formais e Autômatos - A01
10