|
|
|
|
BCC241 – LINGUAGENS FORMAIS E
AUTOMATOS NOTAS
ATENÇÃO:
A ÚLTIMA PROVA FOI ADIADA PARA DIA 15/12
|
Introdução: “Quais são as capacidades
e limitações de um computador?” Essa é a questão fundamental da Teoria da Computabilidade. A resposta para esta questão é
fundamentada em modelos formais para o conceito de computação. O estudo
desses modelos e de restrições dos mesmos leva a uma hierarquia de
classificação de linguagens em relação à dificuldade de processamento das
mesmas – o que é conhecido como Hierarquia
de Chomsky. Os resultados teóricos obtidos nesse estudo sobre o
processamento de linguagens constituem a base para a implementação de
compiladores e são o objeto de estudo nesse curso.
|
|
Bibliografia:
▪
Newton José
Vieira, Introdução
aos Fundamentos de Teoria da Computação, Thomson,
2006
▪ Michael Sipser, Introduction to the
Theory of Computation, 2005.
Outras referências:
▪ Thomas
A. Sudkamp, Languages and Machines: An Introduction
to the Theory of Computer Science, Addison Wesley 1996.
▪ Harry R. Lewis & Christos H. Papadimitriou, Elements
of the Theory of Computation (2nd Edition),
Prentice Hall, 1997.
▪
Livro
interessante sobre a história do desenvolvimento das idéias em computabilidade: Martin Davis, The Universal Computer: The
Road from Leibniz to Turing, W.W. Norton & Company, 2000.
Links úteis:
|
Programa, slides e exercícios:
|
Data
|
Assunto
|
Slides
|
Exercícios
|
|
11/08
|
Introdução:
|
|
|
|
16/08
18/08
|
Alfabetos, Strings, Linguagens
e Gramáticas
Cap1: seções 1.10, 1.11,
1.12
|
ftc01.pdf
|
pag.44: 1 a 12
pag. 50: 1 a 5
|
|
23/08
25/08
|
DFA - Autômato Finito
Determinista
LR - Linguagem Regular
Minimização de DFAs
Cap2: seções 2.1, 2.2.1 e
2.2.2
|
ftc02a.pdf
|
pag. 81: 1,2,3,10,
11,12,16,17,18
|
|
30/08
01/09
|
NFA - Autômato Finitos Não Determinista
Equivalência NFA ó DFA
Propriedades de fecho de
linguagens regulares
Cap2: seções 2.2.3, 2.3.1
e 2.3.2
|
ftc02b.pdf
|
pag 97: 1,2,5,7c,9
|
|
27/09
29/09
|
Semana de Estudos CACIC
|
|
|
|
04/10
06/10
|
Revisão
Prova 1
|
|
pag 128: 1,2,6,8
pag 129: 9,14,21
|
|
29/09
13/10
|
Linguagens Regulares: Lema do bombeamento
Cap2: seção 2.4
|
ftc03a.pdf
|
pag 102: 2, 3,
4, 7
|
|
18/10
20/10
|
Expressões Regulares
Equivalência DFA óExpressões regulares
Cap2: seção
2.6
|
ftc03b.pdf
|
pag 118: 2, 3,
4, 5
|
|
25/10
27/10
|
Gramáticas
Hierarquia de Chomsky
Gramáticas Regulares
Cap 2:
seção 2.7
|
ftc04.pdf
|
pag 123:
1,3,4,8
pag 136:
1,2,6,8,9,14
|
|
03/11
|
Prova 2
|
|
|
|
08/11
10/11
|
CFG - Gramática Livre de Contexto
CFL - Linguagem Livre de Contexto
Árvore de derivação, ambigüidade
Cap 3:
seções 3.4,3.4.1,3.4.2
|
ftc05a.pdf
|
pag 187:1,
2,3,4,5,
pag. 197: 13, 14, 15, 17
|
|
15/11
|
Recesso escolar
|
|
|
|
17/11
|
Formas Normais de CFLs
Forma Normal de Chomsky
Forma Normal de Greibach
Cap. 3: seções 3.4.3,
|
ftc05b.pdf
|
Pag. 187: 6,7,8,9,10,11
|
|
22/11
|
Propriedades de CFLs
Cap 3:
seção 3.5
|
ftc05c.pdf
|
pag. 194: 6,7,8
pag. 199: 27
|
|
24/11
|
Prova 3
|
|
|
|
26/11
29/11
|
Lema do bombeamento para CFLs
Cap 3:
seção 3.5
|
ftc05c.pdf
|
pag. 194: 1,2,3,4,5
pag. 198: 22, 23
pag. 199: 25, 26
|
|
01/12
06/12
|
PDA - Automato de pilha
CFL x PDA
Cap 3:
seções 3.1, 3.2. 3.4.4,
|
ftc06.pdf
|
pag. 147: 3, 4
pag. 154: 1, 3
pag. 195: 1,3
pag. 198: 18
|
|
08/12
|
Parsing
|
|
|
|
15/12
|
Prova 4 (exceto pumping
lema para CFLs)
|
|
|
|
20/12
|
Exame Especial
|
|
|
Exercícios adicionais:
|
|
|
