MATA50

Linguagens Formais e Autômatos

Sobre:

MATA50 faz parte da lista de disciplinas da área de Fundamentos e Teoria da Computação que aborda os aspectos teóricos fundamentais para a Ciência da Computação. Nesta disciplina, abordamos alguns resultados fundamentais sobre representabildiade de conjuntos e funções através de sistemas formais finitários e suas conexões com a Álgebra, a Combinatória, a Lógica, entre outros. São tópicos concernentes a essa disciplina: linguagens formais, autômatos, Expressões RegularesDeseja-se com essa disciplina desenvolver as seguintes habilidades:

  • Manipular as linguagens e ferramentais da Matemática Discreta
  • Manipular representações formais de objetos através de procedimentos computacionais
  • Representar procedimentos computacionais através de manipulação formal de símbolos
  • Estabelecer conexões entre a teoria dos algoritmos e complexidade computacional e suas representações teóricas na Teoria das Linguagens Formais

Programa

Ementa

Conceito de linguagem. Hierarquia de Chomsky. Linguagens regulares e expressões regulares. Reconhecedores, geradores e propriedades das linguagens discriminadas na hierarquia de Chomsky. Ambiguidade e simplificação de gramáticas livres de contexto. Formas normais de gramáticas livres de contexto.

Objetivo

Introduzir o conceito de linguagem formal e estudar as linguagens especificadas na hierarquia de Chomsky. Mostrar a importância teórica do estudo destas linguagens. Mostrar a utilização das mesmas e dos modelos relacionados em aplicações computacionais como, por exemplo, na modelagem de problemas e construção de compiladores.

Conteúdo Programático

  1. Motivação do estudo das linguagens formais
    1. Linguagens formais e informais
    2. A hierarquia de Chomsky
    3. Uma visão geral do uso e importância das linguagens e modelos estudados na hierarquia de Chomsky
    4. Especificação de linguagens de programação e compiladores
  2. Conceito de linguagem formal.
    1. Alfabeto, palavra, fecho de Kleene, linguagem.
  3. Linguagens regulares
    1. 3.1. Expressões regulares
    2. Gramáticas regulares
    3. Autômato finito determinista
    4. Minimização de autômatos finitos
    5. Autômato finito determinista com saída: máquinas de Moore e Mealy
    6. Autômato finito não determinista
    7. Equivalência entre autômatos finitos, gramáticas regulares e expressões regulares
    8. Propriedades de linguagens regulares
    9. Lema do bombeamento.
  4. Linguagens livres de contexto
    1. Autômato de pilha
    2. Gramáticas livres de contexto (GLC)
    3. Derivações mais a direita e mais à esquerda
    4. Árvores de análise sintática
    5. Ambiguidade de GLC
    6. Simplificação de GLC
    7. Formas normais de Chomsky e Greibach
    8. Equivalência entre autômatos de pilha e GLC
    9. Propriedades de linguagens livres de contexto
    10. Lema do bombeamento
  5. Introdução aos problemas de decisão
    1. Exemplo de problemas decidíveis relativos às linguagens estudadas
    2. Exemplos de problemas indecidíveis relativos às linguagens estudadas

Bibliografia

1. Linguagens Formais: teoria, modelagem e implementação. Marcus Vinícius Midena Ramos, João José Neto, Ítalo Santiago Veja. Bookman, 2009. 2. Linguagens Formais e Autômatos. Paulo Blauth Menezes. Editora Sagra Luzzatto. Série Livros Didáticos – Instituto de Informática da UFRGS. 3. Introdução à Teoria de Autômatos, Linguagens e Computação. John E. Hopcroft, Jeffery D. Ullman; Rajeev Motwani. Tradução da segunda edição americana. Editora Campus. 2003 4. Elementos de Teoria da Computação. (original: Elements of the Theory of Computation. Prentice-Hall, Inc., 1998). HARRY R. Lewis, Christos H. Papadimitriou. Editora Bookman. 5. Machines, Languages and Computation. Peter J. Denning; Jack B. Dennis; Joseph E. Qualitz. Prentice-Hall. 1978. 6. Compilers: Principles, Techniques, and Tools. Alfred V., Monica S. Lam, Ravi Sethi, Jeffrey D. Ullman. Addison Wesley; 2nd edition, 2006.

Recursos