Linguagens Formais

Segundo Semestre de 2008

Horário: 3as e 5as, 10:00 - 12:00

Local das aulas: sala F2-010

Prof. Fábio Protti  

Onde me achar: sala E-2009 do DCC (ramal 9520)  

 

Tópicos do Curso

• Linguagens e expressões regulares. Gramáticas lineares à direita.
• Autômatos finitos determinísticos e não determinísticos.
• Gramáticas e linguagens livres de contexto.
• Autômatos de pilha.
• Linguagens recursivas e recursivamente enumeráveis.
• Máquina de Turing. Funções computáveis.
• Problema da Parada. Tese de Church-Turing. Hierarquia de Chomsky.

 

Bibliografia

• H. R. Lewis e C. H. Papadimitriou. Elementos de Teoria da Computação. Ed. Bookman, segunda edição.
• J. E. Hopcroft e J. Ullman. Introduction to Automata Theory, Languages and Computation. Ed. Addison-Wesley.
• P. F. Blauth Menezes. Linguagens Formais e Autômatos. Inst. de Informática da UFRGS. Editora Sagra Luzzatto, Porto Alegre, quarta edição. 
• Judith L. Gersting. Fundamentos Matemáticos para a Ciência da Computação. LTC Editora, Rio de Janeiro. (Capítulo 8)
• Notas de aula do Prof. Collier

 

Calendário de Provas 

Primeira Prova: dia  25 de setembro de 2008 

Segunda Prova: dia 20 de novembro de 2008 (inclui apenas a segunda parte da matéria)

Segunda Chamada: dia 27 de novembro de 2008  (inclui a matéria toda)

A Segunda Chamada é para quem perdeu prova.

 

Avaliação

Suponha que P1 e P2 sejam as notas das duas Provas, 

e T seja a nota do Trabalho de Implementação.

A nota final será  (3*P1 + 3* P2 + T) / 7.

 

Listas - para estudar

Não é obrigatório entregar as listas.

Lista 1

Lista 2  

Programas -- Trabalho de implementação

Haverá três programas. 

Os programas podem ser feitos em grupos de dois alunos.

O prazo para entrega dos programas é 23 de novembro (até meia-noite).

 

Prog1 e Prog2   

Primeiro, você deve se cadastrar em http://acm.uva.es.

Depois, escolha dois dentre os problemas abaixo:    

http://acm.uva.es/p/v3/325.html

http://acm.uva.es/p/v3/328.html

http://acm.uva.es/p/v3/384.html

http://acm.uva.es/p/v6/673.html

Envie seus programas ao juiz on-line.

Depure-os bem. 

Finalmente, envie para mim por e-mail os fontes em formato texto. 

 

Prog3

Use o Simulador de Máquinas de Turing Universais que está disponível na página do Prof. Collier.

 

ENUNCIADO DO PROGRAMA:

A definir

Depure bem este programa, e envie-o para mim por e-mail.    

Monitor 

A definir