Teoria de Linguagens
Segundo semestre/2005

• 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; veja como usar .
  • Deus ex Machina
  • Turing's World
  • Webworks Laboratory
  • Ganimal
  • The Java Computability Toolkit
  • Turing Machine (C++ Simulator)
• Veja uma demonstração poética da indecidibilidade do problema da parada (em PS).
• ANTLR: a framework for constructing recognizers, compilers, and translators from grammatical descriptions containing Java, C#, or C++.
• Listas de exercícios:
  • Primeira Lista. Entrega: 13/09/2005.
  • Segunda Lista. Entrega: 17/10/2005.
  • Terceira Lista. Entrega: 21/11/2005.
• Provas:
  • Primeira Prova:
    • Data: 15/09.
    • Assunto: Até item 2.4, inclusive.
    • Veja a solução do professor. (Para quem pegou a solução antes de 15h de 30/9: na questao 3(a), 3a linha de delta1, substitua i1 por i; e na 4a linha, substitua p1 por p.)
  • Segunda Prova:
    • Data: 18/10.
    • Assunto: Até capítulo 3, inclusive.
  • Terceira Prova:
    • Data: 22/11.
    • Assunto: Até capítulo 5, inclusive.
  • Prova Suplementar (não obrigatória):
    • Data: 06/12.
    • Assunto: Toda a matéria.
    • Valor: 18 pontos.
    • Importante: a nota substituirá a menor das 3 notas anteriores.
• Seminários:
  Dia 29/11:
  1. Applications of finite automata representing large vocabularies.
     Álvaro Rodrigues Pereira Júnior.
  2. Probabilistic Turing Machines.
     Horácio Antônio Braga Fernandes de Oliveira.
  3. Autômatos estocásticos
     Bruno Santos Pimentel.
  4. Autômatos adaptativos.
     David Braga Fernandes de Oliveira.
  5. Recuperação da Arquitetura de Software usando Máquina de Estado.
     Thiago Henrique Braga.
  6. Autômato de Pilha para processamento de consultas XPath em documentos XML.
     Denilson Alves Pereira.
  7. Tree Automata.
     Leonardo Chaves Dutra da Rocha.
  8. Modelagem Automática do Comportamento de grupos de Agentes por meio de FSA e PDA.
     Marcelo Borghetti.
  Dia 30/11:
  1. Natural computation and non-Turing models for computation.
     Renato Vimieiro.
  2. LOTOS: Language of Temporal Ordering Specifications.
     Moisés Gomes de Carvalho.
  3. Hypercomputation - philosophical issues.
     João Paulo Domingos Silva.
  4. Timed automata.
     José Augusto Miranda Nacif.
  5. Automatos celulares.
     Daniel Câmara.
  6. Algoritmos baseados em autômatos para casamento de padrões.
     Max do Val Machado.
  7. Uma introdução a ASMs (Abstract State Machines).
     Wagner Salazar Pires.
  Dia 01/12:
  1. A Finite State Automata Based Technique for Protein Classification Rules Induction.
     Adriano Alonso Veloso.
  2. Parsing Expression Grammars.
     Sérgio Vale e Pace.
  3. L-Systems.
     Ricardo Augusto Rabelo Oliveira.
  4. DNA computing.
     Alex Borges Vieira.
  5. Compactação de funções de transição em autômatos finitos.
     Leonardo Teixeira Passos.
  6. Redes de Petri: propriedades e aplicações.
     Fabrício Vivas Andrade.
  7. Construção incremental de autômatos de estado finito mínimos.
     Fabiano Cupertino Botelho.
• Veja suas notas.