Teoria de Linguagens
Primeiro semestre/2002 - curso oferecido na FUCAPI/Manaus

• Plano de curso: HTML; PostScript (Para leitura de PostScript, pegue o software apropriado.)
• A página da profa. Susan H. Rodger contém referências para ferramentas que podem ser utilizadas para o estudo de alguns conceitos.
• Apostila: Não mais disponivel.
  • Capítulo 1: Conceitos Preliminares
  • Capítulo 2: Máquinas de Estado-Finito
  • Capítulo 3: Autômatos com Pilha
  • Capítulo 4: Máquinas de Turing
  • Capítulo 5: Decidibilidade
• Veja uma demonstração poética da indecidibilidade do problema da parada (em PS).
• Listas de exercícios:
  • Primeira Lista. Entrega: 29/04/2002.
  • Segunda Lista. Entrega: 10/06/2002.
  • Terceira Lista. Entrega: 12/07/2002.
• Provas:
  • Primeira Prova:
    • Data: 29/04.
    • Assunto: Até item 2.4, inclusive.
    • Veja a solução do professor.
  • Segunda Prova:
    • Data: 10/06.
    • Assunto: Até capítulo 3, inclusive.
  • Terceira Prova:
    • Data: 12/07.
    • Assunto: Até capítulo 5, inclusive.
• Veja o trabalho prático (em PostScript). Demonstração em 10/06/2002.
• Monografias devem ser entregues até 05/07/2002.
  Exemplos de tópicos para monografias:
  • Alternating automata
  • Attribute grammars.
  • Cellular automata.
  • DNA Computing
  • Picture description grammars
  • Quantum Computing (ver ACM Computing Surveys, 32(3), Sep. 2000)
  • Lambda-calculus
  • Lindenmayer systems (L-systems)
  • Sistemas de reescrita
  • Teorema da incompletude de Godel
  • Teoria dos tipos
  • Timed automata
  • Tree automata
• Veja suas notas.