Skip to content

Latest commit

 

History

History
147 lines (105 loc) · 8.36 KB

README.md

File metadata and controls

147 lines (105 loc) · 8.36 KB
Raw

Linguagens Formais e Autômatos

1° SEM 2025

Ementa

  • INTRODUÇÃO A LINGUAGENS FORMAIS E AUTÔMATOS

    • ELEMENTOS DE MATEMÁTICA DISCRETA

      • Elementos de Matemática Discreta: Conjuntos Enumeráveis
      • Elementos de Matemática Discreta: Conjuntos.
      • Elementos de Matemática Discreta: Relações e Funções
      • Teoremas e Demonstraçoes

    • CONCEITOS BÁSICOS DE LINGUAGENS

      • Alfabetos, palavras
      • Cadeias e concatenação de cadeias
      • Linguagens
      • Operações sobre Linguagens

    • LINGUAGENS FORMAIS E GRAMÁTICAS

      • Derivação
      • Gramática
      • Hierarquia de Chomsly
      • Linguagem Gerada por uma Gramática

  • LINGUAGENS, GRAMÁTICAS E EXPRESSÕES

    • LINGUAGENS REGULARES

      • Fechamento de Linguagens Regulares sob união e fecho de Kleene
      • Gramáticas Regulares
      • Identificação de Linguagens Regulares
      • Linguagens Regulares: Definição Formal

    • AUTÔMATOS FINITOS

      • Autômatos Finitos Determinísticos
      • Autômatos Finitos Não-Determinísticos
      • Fechamento de Linguagens Regulares sob complemento e interseção
      • Minimização de Autômatos Finitos

    • EXPRESSÕES REGULARES

      • Conversão de autômatos finitos para expressões regulares
      • Conversão de expressões regulares para autômatos finitos
      • Definição e exemplos de expressões regulares
      • Expressões Regulares POSIX

  • LINGUAGENS E GRAMÁTICAS LIVRES DO CONTEXTO E AUTÔMATOS COM PILHA

    • GRAMÁTICAS LIVRES DE CONTEXTO

      • Árvores de derivação
      • Definição e características de Gramáticas Livres de Contexto
      • Derivações mais à esquerda e mais à direita
      • Gramáticas ambíguas e linguagens inerentemente ambíguas

    • LINGUAGENS LIVRES DE CONTEXTO

      • Definição de Linguagens Livres de Contexto
      • Fechamento de Linguagens Livres de Contexto sob fecho de Kleene
      • Fechamento de Linguagens Livres de Contexto sob união
      • Manipulação de gramáticas

    • AUTÔMATOS COM PILHA

      • Autômatos com pilha determinísticos
      • Configurações, aceitação por estado final e aceitação por pilha vazia
      • Conversão de gramáticas livres de contexto para autômatos com pilha
      • Definição Formal de Autômatos com Pilha

  • LINGUAGENS SENSÍVEIS AO CONTEXTO E RECURSIVAMENTE ENUMERÁVEIS

    • LINGUAGEM SENSÍVEL AO CONTEXTO

      • Definição de Linguagem Sensível ao Contexto
      • Fechamento de Linguagem Sensível ao Contexto sob fecho de Kleene
      • Fechamento de Linguagem Sensível ao Contexto sob união
      • Gramática sensível ao contexto

    • MÁQUINAS DE TURING

      • Configurações e aceitação
      • Definição de Máquinas de Turing
      • Reconhecimento de linguagens regulares e livres de contexto
      • Reconhecimento de linguagens sensíveis ao contexto

    • MÁQUINAS DE TURING E RECURSIVIDADE

      • Aceitação de linguagens geradas por gramáticas arbitrárias
      • Linguagens não recursivas
      • Linguagens recursivas
      • Tese de Church

Referências

Basica

  • GARCIA, A. de V.; HAEUSLER, E. H. Linguagens formais e autômatos. Londrina: EDA, 2017.
  • HOPCROFT, J. E.; ULLMAN, J. D.; MOTWANI, R.; SOUZA, V. D. de. Introdução à teoria dos autômatos, linguagens e computação. 2.ed. Rio de Janeiro: Elsevier, 2002.
  • LOUDEN, K. C.; SILVA, F. S. C. Compiladores: Princípios e práticas. São Paulo, Brasil: Thomson, 2004. p. 569(569).
  • SETZER, V. W.; MELO, I. S. H. de. A Construção de um Compilador. Rio de Janeiro: Campus, 1989. Disponível em: https://www.ime.usp.br/~vwsetzer/ .
  • SIPSER, M. Introdução á teoria da computação. 2. ed. São Paulo: Cengage, 2022.

Complementar

  • AHO, A. V.; LAM, M. S.; SETHI, R.; ULLMAN, J. D. Compiladores: Princípios, técnicas e ferramentas. 2. ed. São Paulo, Brasil: Pearson Addison Wesley, 2007. p. 634(634).
  • ANDERSON, J. A. Automata Theory with Modern Applications. Cambridge: Cambridge University Press, 2006.
  • JENSEN, A. R.; MADACHY, E. W. Computation and automata. Cambridge: Cambridge University Press, 1979.
  • LEWIS, H. R.; PAPADIMITRIOU, C. H. Elementos De Teoria Da Computacao. 2ª edição. São Paulo: Bookman, 2004.
  • MENEZES, P. B. Linguagens formais e autômatos. 5. ed. Porto Alegre, Brasil: Bookman, 2008. p. 215(215).
  • PIERCE, B. C. Basic category theory for computer scientists. Cambridge: MIT Press, 1991(Foundations of computing).
  • RICH, E. Automata, Computability and Complexity: Theory and Applications. São Paulo: Prentice Hall, 2008.
  • ROSA, J. L. G. Linguagens formais e autômatos. 1. ed. Rio de Janeiro, Brasil: LTC, 2010.
  • SEBESTA, R. W. Concepts of programming languages. 6. ed. Boston: Addison Wesley, 2003.
  • SHALLIT, J. A second course in formal languages and automata theory. Cambridge, UK: Cambridge University Press, 2008.
  • SUDKAMP, T. A. Languages and machines: An introduction to the theory of computer science. 3. ed. Boston: Addison Wesley, 2005.
  • ULLMAN, J. D.; MOTWANI, R.; HOPCROFT, J. E. Introduction to automata theory, languages, and computation. 3. ed. Boston, USA: Pearson, 2006. p. 535(535).
  • YAN, S. Y. An introduction to formal languages and machine computation. Singapore: World Scientific Publishing Company, 1998.

Artigos

Links de interesse

  • Valdemar Setzer (USP - Universidade de São Paulo). Materiais didáticos sobre teoria da computação e linguagens formais. http://www.ime.usp.br/~vwsetzer/
  • João L. G. Rosa (UFRJ - Universidade Federal do Rio de Janeiro). Professor de Computação com material de apoio para cursos de linguagens formais e autômatos. http://www.dcc.ufrj.br/~jorge
  • Alfred V. Aho (University of Arizona). Autor de livros amplamente usados em cursos de automatos e linguagens formais, como "Compilers: Principles, Techniques, and Tools". https://www.cs.arizona.edu/~aho/
  • Michael Sipser (MIT - Massachusetts Institute of Technology). Autor do famoso livro "Introduction to the Theory of Computation", que aborda automatos e linguagens formais. https://people.csail.mit.edu/sipser/
  • Douglas Comer (Purdue University). Leciona sobre teorias de computação e linguagens formais, e tem material de suporte acessível online. https://www.cs.purdue.edu/homes/comp

Vídeos de interesse