Teoria de Linguagens
Segundo semestre/2009

• Livro texto: Introdução aos Fundamentos da Computação, Pioneira Thomson Learning, 2006.
  O livro está sendo vendido na Livraria da UFMG, Praça de Serviços.
  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.
• 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)
• Veja um texto bom e conciso sobre demonstrações de teoremas. Ele foi baixado de http://www.math.dartmouth.edu/archive/m38s04/public_html/. Observe, particularmente, os itens 4 e 7 da seção 3!
• Veja algumas técnicas de prova que nunca devem ser usadas...
• 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: 21/09.
    • Assunto: Até item 2.4, inclusive.
    • Valor: 26 pontos (ou 18; veja a lista preparatória).
    • Veja a lista preparatória a ser entregue até o dia 21/09, 16:40h.
    • Veja a solução do professor.
  • Segunda Prova:
    • Data: 04/11.
    • Assunto: Até capítulo 3, inclusive.
    • Valor: 27 pontos (ou 18; veja a lista preparatória).
    • Veja a lista preparatória a ser entregue até o dia 04/11.
  • Terceira Prova:
    • Data: 02/12.
    • Assunto: Até capítulo 5, inclusive.
    • Veja a lista preparatória a ser entregue até o dia 02/12.
  • Prova Suplementar (não obrigatória):
    • Data: 16/12.
    • Assunto: Toda a matéria.
    • Valor: 30 pontos (3 extra).
    • Importante: a nota substituirá a menor das 3 notas anteriores (considerando Li+Pi).
• Seminários:
  1. Definição do tema: até 25/11.
  2. Sorteio das apresentações: 25/11.
  3. Entrega da monografia (como especificada no Plano de Curso) até o dia 30/11. Adiada para 7/12. Adiada para 9/12.
• Seminários a serem apresentados no dia 09/12:
  1. Análise de strings para PHP
     Andrei Rimsa Álvares
  2. Grammatically-based genetic programming
     Daniel Hasan Dalip
  3. Domain-specific languages.
     Marcos Rodrigo Sol Souza.
  4. Can abstract state machines be useful in language theory?
     André Luiz Camargos Tavares
  5. Tetris and decidability
     Rafael Santin
  6. Sistemas imunológicos artificiais
     Allan Jones Costa e Silva
• Seminários a serem apresentados no dia 14/12:
  1. Autômatos celulares
     Marcos Henrique Fonseca Ribeiro
  2. Probabilistic automata
     Anderson Grandi Pires
  3. Redes de Petri
     Marisa Affonso Vasconcelos
  4. Autômatos adaptativos
     Renê Rodrigues Veloso
  5. Towards a theory of intelligence
     Giselle Machado Nogueira Reis
  6. Obtaining shorter regular expressions from finite-state automata
     Fernando Afonso Santos
  7. Timed automata
     Marcelo Gabriel Almiron
• 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:
  1. Ackerman, M., Shallit, J., Efficient enumeration of words in regular languages Theoretical Computer Science 410, 2009, pp. 3461-70.
  2. Ben-Davida, S., Fismanb, D., Ruahc, S. Embedding finite automata within regular expressions, Theoretical Computer Science 404, 2008, pp. 202-218.
  3. Campeanu, A., Paun, A., Smith, J.R. Incremental construction of minimal deterministic cover automata, Theoretical Computer Science 363, 2006, pp. 124-134.
  4. 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.
  5. Clement, J., Duval, J.-P., Guaiana, G., Perrin, D., Rindone, G. Parsing with a finite dictionary, Theoretical Computer Science 340, 2005, pp. 408-431.
  6. Crespi Reghizzi, S., Pradella, M. Tile rewrinting grammars and picture languages, Theoretical Computer Science 340, 2005, pp. 257-272.
  7. Garcia, P., de Parga, M.V., Álvarez, G.I, Ruiz, J. Universal automata and NFA learning, Theoretical Computer Science 407, 2008, pp. 192-202.
  8. Geeraerts, G., Raskin, J-F., Van Begin, L. Well-structured languages, Acta Informatica 44, 2007, pp. 249-288.
  9. Glabbeek, R.J. On the expressiveness of higher dimensional automata, Theoretical Computer Science 356, 2006, pp. 265-290.
  10. Hierons, R.M. , Canonical finite state machines for distributed systems, Theoretical Computer Science 411, 2010, 566-580.
  11. Hromkovic, J., Shnitger, G. Comparing the size of NFAs with and without e-transitionss, Theoretical Computer Science 380, 2007, pp. 100-114.
  12. Jurdzinski, T., Otto, F. Restarting automata with restricted utilization of auxiliary symbols, Theoretical Computer Science 363, 2006, pp. 162-181.
  13. Jurgensen, H., Staiger, L., Yamasaki, H. Finite automata enconding geometric figures, Theoretical Computer Science 381, 2007, pp. 33-43.
  14. Kao, J.-Y., Rampersad, N., Shallit, J. On NFAs where all states are final, initial, or both, Theoretical Computer Science 410, 2009, pp. 5010-21.
  15. Kari, J. Theory of cellular automata: A survey, Theoretical Computer Science 334, 2005, pp. 3-33.
  16. Kutrib, M., Malcher, A. Context-dependent nondeterminism for pushdown automata, Theoretical Computer Science 376, 2007, pp. 101-111.
  17. Kutrib, M., Malcher, A., Werlein, L. Regulated nondeterminism in pushdown automata, Theoretical Computer Science 410, 2009, pp. 3447-60.
  18. Malcher, A. Minimizing finite automata is computationally hard, Theoretical Computer Science 327, 2004, pp. 375-390.
  19. Neary, T., Woods, D. Small fast Turing machines, Theoretical Computer Science 362, 2006, pp. 171-195.
  20. 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.
  21. Panduranga Rao, M.V. Interference automata, Theoretical Computer Science 403, 2008, pp. 89-103.
  22. Salomaa, K., Yu, S., Zan, J. Deciding determinism of caterpillar expressions Theoretical Computer Science 410, 2009, pp. 3438-46.
  23. Timmis, J., Hone, A., Stibor, T., Clark, E. Theoretical advances in artificial immune systems, Theoretical Computer Science 403, 2008, pp. 11-32.
  24. van Zijl, L. Generalized acceptance, succinctness and supernondeterministic finite automata, Theoretical Computer Science 313, 2004, pp. 159-172.
• Veja suas notas.