Print - - Edit

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

Google Meets, 4a. e 6a de 09:00 h às 10:40.

Playlist no YouTube com alguns vídeos sobre o curso: https://bit.ly/32OUQNZ.

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

Critério de avaliação

Avaliação continuada no Google Classroom

  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.
Page last modified on August 28, 2020, at 05:44 PM