UNIVERSIDADE DE SÃO PAULO
INSTITUTO DE CIÊNCIAS MATEMÁTICAS E DE COMPUTAÇÃO
CURSO DE CIÊNCIAS DE COMPUTAÇÃO
SCE0185
TEORIA DA COMPUTAÇÃO E
LINGUAGENS FORMAIS
Prof. João Luís Garcia Rosa
2o. semestre de 2008
I. EMENTA
Estudo detalhado das linguagens formais. Relação entre autômatos e classes de linguagens. Problemas decidíveis e indecidíveis. Teoria da Computação: Máquina de Turing e complexidade.
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. Autômatos de Estados Finitos
1.6. Autômatos Finitos com Arcos-l
1.7. Minimização de um Autômato Finito
1.8. Autômatos Finitos com Saída
2. LINGUAGENS LIVRES DE CONTEXTO E AUTÔMATOS DE 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 de Pilha
2.6. O Teorema da Equivalência
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 RECURSIVAMENTE ENUMERÁVEIS E MÁQUINAS DE TURING
4.1. Definição de Gramáticas Irrestritas
4.2. Das Gramáticas para as Máquinas de Turing
4.3. Das Máquinas de Turing para as Gramáticas
4.4. A Máquina de Turing Universal
4.5. Máquinas de Turing Não Determinísticas
4.6. Técnicas para Construção de Máquinas de Turing
5. TEORIA DA COMPUTAÇÃO
5.1. Poder das Máquinas de Turing
5.2. Tese de Church-Turing
5.3. O Problema da Parada e a Indecidibilidade
5.4. Teoria da Complexidade
III. AVALIAÇÃO
3 provas:
P1 = 18/09 (turma 1-A); 19/09 (turma 2-B)
P2 = 06/11 (turma 1-A); 07/11 (turma 2-B)
P3 = 11/12 (turma 1-A); 12/12 (turma 2-B)
Exercícios e Trabalhos Práticos, com implementação: T1 e T2
Entrega do Trabalho T1:
Entrega do Trabalho T2:
Seminários T3: durante o semestre.
MP = P1 * 0,4 + P2 * 0,3 + P3 * 0,3
MT = (T1 + T2 + T3) / 3
MF = Média Final :
Se
MP ³ 5 e MT ³ 5 então MF =
(7*MP + 3*MT)/10
Se MP < 5 ou
MT < 5 então MF =
menor valor entre MP e MT
|
Norma de Recuperação |
|
1 prova de recuperação PR Realização: Até a primeira semana de aulas
do semestre posterior. Critério de Aprovação: Média = MF + (PR/2,5), se
PR >= 7,5; ou Média = Max {MF, PR}, se
PR < = 5,0; ou Média = 5,0, se 5,0 <= PR < 7,5. |
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-A: Segundas/Quintas: 8h10-9h50 – sala 5104
Turma 2-B: Terças/Sextas: 10h10-11h50 – sala 5103
IV. BIBLIOGRAFIA
·
Hopcroft, J. E. and Ullman, J. D. (1969), Formal Languages and Their
Relation to Automata, Addison-Wesley Publishing Company.
·
Hopcroft, J. E., Ullman,
J. D. e Motwani, R. (2003), Introdução à Teoria de
Autômatos, Linguagens e Computação. Tradução da segunda edição americana. Editora Campus.
·
Sipser,
M. (2006), Introduction to the Theory of
Computation. Second Edition. Thomson.
· Mealy,
G. H. (1955), “A method for synthesizing sequential circuits,’’ Bell Systems
Technical Journal 34:5, pp. 1045-1079.
·
Menezes, P. B. (1997), Linguagens
Formais e Autômatos. Série Livros Didáticos. 4ª. Edição. Instituto de Informática da UFRGS. Editora
Sagra Luzzatto.
· Moll,
R. N., Arbib, M. A., and Kfoury,
A. J. (1988), An Introduction to Formal
Language Theory, Springer-Verlag.
· Moore,
E. F. (1956), “Gedanken experiments on sequential
machines,” in C. E. Shannon and J. McCarthy (Eds.), Automata Studies,
Princeton University Press, pp. 129-153.
· Taylor, R. G. and Taylor, S. (1997), Models of Computation and Formal Languages, Oxford University Press. Deus Ex Machina: www.ics.uci.edu/~savoiu/dem/
· Diagrama de Estados: JFLAP Version 6.0. www.jflap.org.
Material disponível:
Slides disponíveis
0. Apresentação
1. LINGUAGENS REGULARES E AUTÔMATOS FINITOS
2. LINGUAGENS LIVRES DE CONTEXTO E AUTÔMATOS DE PILHA
3. LINGUAGENS SENSÍVEIS AO CONTEXTO E AUTÔMATOS LIMITADOS LINEARMENTE
4. LINGUAGENS RECURSIVAMENTE ENUMERÁVEIS E MÁQUINAS DE TURING
5. TEORIA DA COMPUTAÇÃO
Listas de Exercícios:
Lista 1
Lista 2
Lista 3
Lista 4
Trabalhos:
Trabalho T1
Trabalho T2
Links Interessantes:
Atualização: 23/07/2008