TCC 00.178 - Linguagens Formais e Teoria da Computação

Sala 206, 2a. e 4a. de 11:00 h às 12:40.

Monitor: Erick Simas Grilo (simas_grilo AT id DOT uff DOT br)
Agendar atendimento por email.

Objetivo

Apresentar conceitos básicos da teoria de autômatos e computabilidade.

Tópicos

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 linearmente limitados
4. Linguagens recursivamente enumeráveis e Máquinas de Turing
5. Introdução à computabilidade

Datas importantes

• P1 08/05/17
• P2 03/07/17
• VS 17/07/17

Critério de avaliação

1. Duas provas (P1 e P2) e uma verificação suplementar (VS).
2. Seja a média das provas (MP) = (P1+P2)/2.
   1. Se MP ≥ 6, o aluno está aprovado.
   2. Se MP < 4, o aluno está reprovado.
   3. Se 4 ≤ MP < 6, o aluno deve fazer VS, ficará aprovado se VS ≥ 6 e reprovado caso contrário.

Referência principal

• Paulo Blauth Menezes, Linguagens Formais e Autômatos, Série livros didáticos, no. 3, 6a. Ed., Instituto de Informática da UFRGS, Bookman, 2011.

Referências auxiliares

• Funções recursivas parciais: H. Enderton, Computability Theory, 2011, Cap. 2.
• Funções recursivas parciais e máquinas de Turing: R. Epstein e W. Carnielly, Computability, 3a. ed, 2008, Cap. 18.
• John E. Hopcroft, Rajeev Motwani, Jeffrey D. Ullman, Introduction to Automata Theory, Languages and Computation, 2nd. Edition, Addison Wesley, 2001.
• Harry R. Lewis e Christos H. Papadimitriou, Elementos de Teoria da Computação, 2a. ed, Bookman, 2000.
• José Lucas Rangel, Linguagens Formais, PUC-Rio, 1999, notas de aula.