Teoria de Linguagens
Segundo semestre/2003

• Plano de curso: PostScript (Para leitura de PostScript, pegue o software apropriado.)
• As seguintes páginas podem auxiliar no aprendizado de certos conceitos:
  • Language Emulator
  • JFLAP.
  • Deus ex Machina
  • Turing's World
  • Webworks Laboratory
  • Ganimal
  • The Java Computability Toolkit
  • Turing Machine (C++ Simulator)
• Apostila: PS.
• Veja uma demonstração poética da indecidibilidade do problema da parada (em PS).
• Listas de exercícios:
  • Primeira Lista. Entrega: 29/10/2003.
  • Segunda Lista. Entrega: 01/12/2003.
  • Terceira Lista. Entrega: 28/01/2004.
• Trabalho especial: 5 questões valendo 1,5 pontos extra cada uma. Entrega: 24/11/2003 até as 16 horas.
• Provas:
  • Primeira Prova:
    • Data: 29/10.
    • Assunto: Até item 2.4, inclusive.
    • Veja a solução do professor.
  • Segunda Prova:
    • Data: 10/12.
    • Assunto: Até Capítulo 3, inclusive.
  • Terceira Prova:
    • Data: 28/01.
    • Assunto: Tudo.
• Seminários:
  Grupo 1 (02/02: 16:30h)
  • Cellular automata
    Flávio Luis Cardeal Pádua
  • Learning Automata
    Ricardo Saraiva de Camargo
  • Parsing of context-free languages
    Fabiana Bigão Silva
  • Quantum Computing
    Leonardo Barbosa e Oliveira
  • Linguagens Formais e Imagens Digitais
    Flávio Humberto Cabral Nunes
  • Timed Automata
    Pedro Mitsuo Shiroma
  • João Rafael Moraes Nicola
  Grupo 2 (04/02: 16:30h)
  • Attribute Grammars
    Ademir de Alvarenga Oliveira
  • João Fernando Machry Sarubbi
  • Lindenmayer systems (L-systems)
    Adriano César Machado Pereira
  • Automata theory for XML researchers
    Bruno Augusto Vivas e Pôssas
  • Autômatos Estocásticos
    Paula de Campos Oliveira
  • Alternating automata
    Thiago Ferreira Chaves
  • Tree automata
    Bruno Diniz de Paula
  Grupo 3 (06/02: 14h)
  • Relação entre XML e Gramáticas
    Guilherme Tavares de Assis
  • DNA Computing
    Milene Souza Castro
  • Sistema Celular para Reconhecimento de Padrão Invariante
    Guillermo Cámara Chávez
  • Autômatos Híbridos
    Ruiter Braga Caldas
  • Petri Nets
    Kalina Ramos Porto
• Referências boas para escolha de tópicos para Seminários:
  • Handbook of Formal Languages, vols. 1, 2 and 3., Springer, 1997.
  • Handbook of Theoretical Computer Science, vols. A and B, The MIT Press, 1990.
  • Periódico: Theoretical Computer Science, Elsevier, 14 vols. (28 issues) per year.
• Alguns assuntos de natureza geral para Seminários (veja ambos na primeira ref. acima):
  • Grammars with controlled derivations
  • Stack automata
• Veja suas notas.