Teoria de Linguagens
Segundo semestre/2007

• Livro texto: Introdução aos Fundamentos da Computação, Pioneira Thomson Learning, 2006.
  Veja soluções dos exercícios do capítulo 1 (em um formato provisorio).
  Algumas livrarias com venda on line:
  • Cultura
  • Saraiva
  • Siciliano
• Veja o Plano de Curso (pdf).
• As seguintes páginas podem auxiliar no aprendizado de certos conceitos:
  • Language Emulator
  • JFLAP; veja como usar .
  • Turing's World
  • The Java Computability Toolkit
  • Turing Machine (C++ Simulator)
• ANTLR: a framework for constructing recognizers, compilers, and translators from grammatical descriptions containing Java, C#, or C++.
• Veja uma demonstração poética da indecidibilidade do problema da parada (em PS).
• Provas:
  • Primeira Prova:
    • Data: 24/09.
    • Assunto: Até item 2.4, inclusive.
    • Veja a solução do professor.
  • Segunda Prova:
    • Data: 24/10.
    • Assunto: Até capítulo 3, inclusive.
    • Veja a lista preparatória a ser entregue até o dia 22/10.
  • Terceira Prova:
    • Data: 26/11.
    • Assunto: Até capítulo 5, inclusive.
    • Veja a lista preparatória a ser entregue até o dia 21/11.
  • Prova Suplementar (não obrigatória):
    • Data: 10/12.
    • Assunto: Toda a matéria.
    • Valor: 27 pontos.
    • Importante: a nota substituirá a menor das 3 notas anteriores.
    • Veja a solução do professor.
• Seminários:
  1. Finite automata enconding geometric figures.
     Antônio da Luz Júnior.
  2. Autômatos híbridos aplicados a redes de sensores sem fio.
     Daniel Ludovico Guidoni
  3. Abstract States machines
     Kecia Aline Marques Ferreira
  4. Finite State Testing and Analysis of Graphical User Inteface
     Humberto César Brandão de Oliveira
  5. Recognizing Behavioral Patterns at Runtime using Finite Automata
     Mariane Moreira de Souza
• 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.)
  • Os melhores periódicos de sua área.
• Alguns assuntos para Seminários:
  • Abdeddaïm, Y., Asarin, E., Maler, O. Scheduling timed automata, Theoretical Computer Science 358, 2006, pp. 104-120.
  • Campeanu, A., Paun, A., Smith, J.R. Incremental construction of minimal deterministic cover automata, Theoretical Computer Science 363, 2006, pp. 124-134.
  • Cherubini, M., Crespi Reghizzi, S., Pradella, M., San Pietro, P. Picture Languages: Tiling systems versus tile rewrinting grammars, Theoretical Computer Science 356, 2006, pp. 90-103.
  • Clement, J., Duval, J.-P., Guaiana, G., Perrin, D., Rindone, G. Parsing with a finite dictionary, Theoretical Computer Science 340, 2005, pp. 408-431.
  • Crespi Reghizzi, S., Pradella, M. Tile rewrinting grammars and picture languages, Theoretical Computer Science 340, 2005, pp. 257-272.
  • Garcia, P., Ruiz, J. Learning in varieties of the form V*LI from positive data, Theoretical Computer Science 362, 2006, pp. 100-114.
  • Geeraerts, G., Raskin, J-F., Van Begin, L. Well-structured languages, Acta Informatica 44, 2007, pp. 249-288.
  • Glabbeek, R.J. On the expressiveness of higher dimensional automata, Theoretical Computer Science 356, 2006, pp. 265-290.
  • Gurevich, Y., Veanes, M., Wallace, C. Can abstract state machines be useful in language theory?, Theoretical Computer Science 376, 2007, pp. 17-29.
  • Han, Y.-S., Wood, D. Obtaining shorter regular expressions from finite-state automata, Theoretical Computer Science 370, 2007, 110-120.
  • Hoogeboom, H.J., Kosters, W.A. Tetris and decidability, Information Processing Letters 89, 2004, pp. 267-272.
  • Hromkovic, J., Shnitger, G. Comparing the size of NFAs with and without e-transitionss, Theoretical Computer Science 380, 2007, pp. 100-114.
  • Jurdzinski, T., Otto, F. Restarting automata with restricted utilization of auxiliary symbols, Theoretical Computer Science 363, 2006, pp. 162-181.
  • Kari, J. Theory of cellular automata: A survey, Theoretical Computer Science 334, 2005, pp. 3-33.
  • Kugel, P. Toward a theory of intelligence, Theoretical Computer Science 317, 2004, pp. 13-30.
  • Kutrib, M., Malcher, A. Context-dependent nondeterminism for pushdown automata, Theoretical Computer Science 376, 2007, pp. 101-111.
  • Malcher, A. Minimizing finite automata is computationally hard, Theoretical Computer Science 327, 2004, pp. 375-390.
  • Neary, T., Woods, D. Small fast Turing machines, Theoretical Computer Science 362, 2006, pp. 171-195.
  • Okhotin, A. An overview of conjunctive grammars, in: Paun, Rozenberg, Salomaa (eds.), Current Trends in Theoretical Computer Science: The Challenge of the Century, vol. II, World Scientific, 2004, pp. 545-566.
  • van Zijl, L. Generalized acceptance, succinctness and supernondeterministic finite automata, Theoretical Computer Science 313, 2004, pp. 159-172.
• Veja suas notas.