Teoria de Linguagens
Segundo semestre/2010

• 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 uma errata
  Veja soluções dos exercícios do capítulo 1 (em um formato provisório).
  Cópias dos slides:
  • Capítulo 1
  • Capítulo 2 até seção 2.3
  • Capítulo 2 da seção 2.4 até o final
  • Capítulo 3 até a seção 3.4
  • Capítulo 3, seção 3.5
  • Capítulo 4
  • Capítulo 5
  Algumas livrarias com venda on line:
  • Cultura
  • Leitura
  • Saraiva
  • Submarino
• 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...
• Veja uma demonstração poética da indecidibilidade do problema da parada (em PS).
• Monitoria:
  • Monitor: Marcelo Gabriel Almiron
  • Atendimento: via e-mail, skype ou presencialmente.
  • Local: sala 3027/DCC-ICEx-UFMG
  • E-mail: malmiron@dcc.ufmg.br
  • Skype: malmiron.dcc.ufmg
• Provas:
  • Primeira Prova:
    • Data: 02/09. Adiada para 09/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 02/09, 16:40h. Adiada a entrega para 09/09, 16:40h.
    • Veja a solução do professor.
  • Segunda Prova:
    • Data: 14/10. Adiada para 19/10. Adiada para 21/10.
    • 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 14/10. Adiada para 19/10. Adiada para 21/10.
  • Terceira Prova:
    • Data: 16/11. Adiada para 18/11. Adiada para 25/11.
    • Assunto: Até capítulo 5, inclusive.
    • Veja a lista preparatória a ser entregue até o dia 16/11. Adiada para 18/11. Adiada para 25/11.
  • Prova Suplementar (não obrigatória):
    • Data: 30/11.
    • 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:
  • Definição do tema: até 04/11.
  • Sorteio das apresentações: 11/11.
  • Entrega da monografia (como especificada no Plano de Curso) até o dia 18/11.
  • Data das apresentações: dia 18/11 para aqueles que quizerem antecipar; dia 23/11, começando às 9h, para os restantes, conforme escala a seguir.
  • Apresentações do dia 18/11 (início às 9:25h):
    1. Cáculo lambda
       Flávio Vinicius Diniz de Figueiredo
  • Apresentações do dia 23/11 (início às 9h):
    1. Finite automata encoding geometric figures
       Carlos Henrique de Carvalho Teixeira
    2. Máquinas de estado abstratas
       Eliseu César Miguel
    3. Domain specific languages
       Rógel Garcia de Oliveira
    4. Theory of cellular automata
       Carlos Alberto Fraga Pimentel Filho
    5. Grammars for music composition
       Felipe Domingos da Cunha
    6. Theoretical advances in artificial immune systems
       Arlei Lopes da Silva
    7. Autômatos adaptativos
       Gildásio Lecchi Cravo
    8. Towards a Formalism for Routing in Challenged Networks
       Vinícius Fernandes Soares Mota
    9. Autômatos quânticos
       Bruno do Nascimento Teixeira
• 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 rewriting 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. Glabbeek, R.J. On the expressiveness of higher dimensional automata, Theoretical Computer Science 356, 2006, pp. 265-290.
  9. Gurevich, Y., Veanes, M., Wallace, C. Can abstract state machines be useful in language theory?, Theoretical Computer Science 376, 2007, pp. 17-29.
  10. Han, Y.-S., Wood, D. Obtaining shorter regular expressions from finite-state automata, Theoretical Computer Science 370, 2007, 110-120.
  11. Hierons, R.M. , Canonical finite state machines for distributed systems, Theoretical Computer Science 411, 2010, 566-580.
  12. Hoogeboom, H.J., Kosters, W.A. Tetris and decidability, Information Processing Letters 89, 2004, pp. 267-272.
  13. Hromkovic, J., Shnitger, G. Comparing the size of NFAs with and without e-transitionss, Theoretical Computer Science 380, 2007, pp. 100-114.
  14. Jurgensen, H., Staiger, L., Yamasaki, H. Finite automata enconding geometric figures, Theoretical Computer Science 381, 2007, pp. 33-43.
  15. 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.
  16. Kari, J. Theory of cellular automata: A survey, Theoretical Computer Science 334, 2005, pp. 3-33.
  17. Kugel, P. Toward a theory of intelligence, Theoretical Computer Science 317, 2004, pp. 13-30.
  18. Kutrib, M., Malcher, A. Context-dependent nondeterminism for pushdown automata, Theoretical Computer Science 376, 2007, pp. 101-111.
  19. Kutrib, M., Malcher, A., Werlein, L. Regulated nondeterminism in pushdown automata, Theoretical Computer Science 410, 2009, pp. 3447-60.
  20. Malcher, A. Minimizing finite automata is computationally hard, Theoretical Computer Science 327, 2004, pp. 375-390.
  21. Neary, T., Woods, D. Small fast Turing machines, Theoretical Computer Science 362, 2006, pp. 171-195.
  22. 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.
  23. Panduranga Rao, M.V. Interference automata, Theoretical Computer Science 403, 2008, pp. 89-103.
  24. Salomaa, K., Yu, S., Zan, J. Deciding determinism of caterpillar expressions Theoretical Computer Science 410, 2009, pp. 3438-46.
  25. Timmis, J., Hone, A., Stibor, T., Clark, E. Theoretical advances in artificial immune systems, Theoretical Computer Science 403, 2008, pp. 11-32.
  26. van Zijl, L. Generalized acceptance, succinctness and supernondeterministic finite automata, Theoretical Computer Science 313, 2004, pp. 159-172.
• Veja suas notas.