Teoria de Linguagens
Segundo semestre/2011

ATENÇÃO: A 3A PROVA E SEMINÁRIOS FORAM REMARCADOS para corrigir engano no cronograma original.
• Livro texto: Introdução aos Fundamentos da Computação, Pioneira Thomson Learning, 2006.
  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 uma demonstração poética da indecidibilidade do problema da parada (em PS).
• Provas:
  • Primeira Prova:
    • Data: 20/09.
    • Assunto: Até item 2.4, inclusive.
    • Valor: 26 pontos.
    • Veja a lista preparatória a ser entregue até o dia 20/9 às 16:40h.
    • Veja a solução do professor.
  • Segunda Prova:
    • Data: 20/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 20/10. ALERTA: será atribuída a nota ZERO para lista contendo cópia de solução minha para qualquer questão. E, neste caso, o valor da prova continuará sendo 18.
  • Terceira Prova:
    • Data: 29/11.
    • Assunto: Até capítulo 5, inclusive.
    • Veja a lista preparatória a ser entregue até o dia 29/11 às 9:25h.
  • Prova Suplementar (não obrigatória):
    • Data: 06/12.
    • Assunto: Toda a matéria.
    • Valor: 27 pontos.
    • Importante: a nota substituirá a menor das 3 notas anteriores (considerando Li+Pi).
• Seminários:
  • Definição do tema: até 03/11.
  • Entrega da monografia: até 17/11.
  • Apresentações: 24/11 e 01/12.
• Seminários a serem apresentados no dia 24/11:
  • Modelagem da unidade de controle do microprocessador MIPS multiciclo através de uma máquina de estados finitos
    Bruno Rodrigues Silva
  • Obtaining shorter regular expressions from finite-state automata
    Emiliana Maria L. Simões
  • Verificação Formal de Propriedades em Redes de Sensores sem Fios utilizando Redes de Petri
    Evellyn Soares Cavalcante
  • Image Storage, Indexing and Recognition with Finite State Automata.
    Kleber Jacques F. de Souza
  • Examining Programmer's Cognitive Skills Using Regular Language
    Maria Lúcia Bento Villela
  • A Cellular Learning Automata Based Clustering Algorithm for Wireless Sensor Networks
    Rodolfo Wanderson L. Coutinho
  • Of robot ants and elephants: A computational comparison
    Tiago de Oliveira Januario
• Seminários a serem apresentados no dia 01/12:
  • Implementação de circuitos lógicos usando autômatos celulares de ponto quântico
    Breno Augusto D. Vitorino
  • Gramáticas Livres de Contexto Probabilísticas: Teoria e Aplicações
    Clayson Sandro F. de S. Celes
  • A Cooperative Congestion Control Approach within VANETs: Formal Verification and Performance Evaluation
    Fernando Augusto Teixeira
  • Verificação de autômatos finitos com o auxílio de provadores de teoremas
    Glauber Modolo Cabral
  • Uma introdução ao lambda-cálculo
    Guilherme Henrique de S. Santos
  • Autômatos celulares aplicados a redes veiculares.
    Ilo Amy Saldanha Rivero
  • Theoretical advances in artificial immune systems
    Rafael Gonçalves Colares
  • Mineração de padrões sequenciais com autômatos finitos probabilísticos
    Thiago Cunha de Moura Salles
  • Autômato celular aplicado ao processamento de imagens: Segmentação, filtragem e compressão
    Virgínia Fernandes Mota
• 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. García, P., de Parga, M.V., Álvarez, G.I, Ruiz, J. Universal automata and NFA learning, Theoretical Computer Science 407, 2008, pp. 192-202.
  8. García, P., López, D., G.I, Ruiz, J., Álvarez, G.I. From regular expressions to smaller NFAs, Theoretical Computer Science 412, 211, pp. 5802-07
  9. Glabbeek, R.J. On the expressiveness of higher dimensional automata, Theoretical Computer Science 356, 2006, pp. 265-290.
  10. Gurevich, Y., Veanes, M., Wallace, C. Can abstract state machines be useful in language theory?, Theoretical Computer Science 376, 2007, pp. 17-29.
  11. Han, Y.-S., Wood, D. Obtaining shorter regular expressions from finite-state automata, Theoretical Computer Science 370, 2007, 110-120.
  12. Hierons, R.M. , Canonical finite state machines for distributed systems, Theoretical Computer Science 411, 2010, 566-580.
  13. Hoogeboom, H.J., Kosters, W.A. Tetris and decidability, Information Processing Letters 89, 2004, pp. 267-272.
  14. Hromkovic, J., Shnitger, G. Comparing the size of NFAs with and without e-transitionss, Theoretical Computer Science 380, 2007, pp. 100-114.
  15. Jurgensen, H., Staiger, L., Yamasaki, H. Finite automata enconding geometric figures, Theoretical Computer Science 381, 2007, pp. 33-43.
  16. 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.
  17. Kari, J. Theory of cellular automata: A survey, Theoretical Computer Science 334, 2005, pp. 3-33.
  18. Kugel, P. Toward a theory of intelligence, Theoretical Computer Science 317, 2004, pp. 13-30.
  19. Kutrib, M., Malcher, A. Context-dependent nondeterminism for pushdown automata, Theoretical Computer Science 376, 2007, pp. 101-111.
  20. Kutrib, M., Malcher, A., Werlein, L. Regulated nondeterminism in pushdown automata, Theoretical Computer Science 410, 2009, pp. 3447-60.
  21. Malcher, A. Minimizing finite automata is computationally hard, Theoretical Computer Science 327, 2004, pp. 375-390.
  22. Neary, T., Woods, D. Small fast Turing machines, Theoretical Computer Science 362, 2006, pp. 171-195.
  23. Okhotin, A. Boolean grammars, Information and Computation 194, 2004, pp. 19-48.
  24. 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.
  25. Panduranga Rao, M.V. Interference automata, Theoretical Computer Science 403, 2008, pp. 89-103.
  26. Salomaa, K., Yu, S., Zan, J. Deciding determinism of caterpillar expressions Theoretical Computer Science 410, 2009, pp. 3438-46.
  27. Shiloni, A., Agmona, N., Kaminkaa, G.A. Of robot ants and elephants: A computational comparison, Theoretical Computer Science 412, 2011, pp. 5771-88.
  28. Timmis, J., Hone, A., Stibor, T., Clark, E. Theoretical advances in artificial immune systems, Theoretical Computer Science 403, 2008, pp. 11-32.
  29. van Zijl, L. Generalized acceptance, succinctness and supernondeterministic finite automata, Theoretical Computer Science 313, 2004, pp. 159-172.
• Veja suas notas.