MATC94

Introdução as Linguagens Formais e Teoria da Computação

MATC94 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 dos resultados fundamentais sobre representabilidade de objetos matematicos através de procedimentos finitários. São tópicos concernentes a essa disciplina: linguagens formais, máquinas de estados finitas, modelos de computação, complexidade computacional, classes de problemas resolvíveis por meios computacionais. Deseja-se com essa disciplina desenvolver as seguintes habilidades:

  • Manipular as linguagens e ferramentas 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
  • Representar problemas computacionais como problemas sobre linguagens
  • Compreender o conceito de procedimento computacional as noções de complexidade associadas
  • Estabelecer conexões entre sistemas de representação, computabilidade e complexidade computacuional

Programa

Ementa

Conceito de linguagem formal. Hierarquia de Chomsky. Linguagens regulares e Livres de Contexto. Expressões regulares. Autômatos finitos, autômatos de pilha. Gramáticas livres de contexto. Noções de análise léxica e sintática de linguagens de programação. Máquinas de Turing. Linguagens recursivamente enumeráveis e recursivas. Noções de decidibilidade. Exemplos de problemas decidíveis e indecidíveis relativos às linguagens da hierarquia de Chomsky. Máquina de Turing como conceito formal de algoritmo. O problema da Parada. A tese de Church. Noções de Teoria de complexidade.

Objetivos

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. Fornecer uma noção de teoria de computabilidade e complexidade. Mostrar o limite da computação na solução de problemas.

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. Expressões regulares
    2. Autômato finito determinista
    3. Minimização de autômatos finitos
    4. Autômato finito não determinista
    5. Autômato finito não determinista com λ-transições
    6. Equivalência entre autômatos finitos e expressões regulares
    7. Gramáticas regulares
  4. Linguagens livres de contexto
    1. Autômato de pilha
    2. Gramáticas livres de contexto (GLC)
    3. Derivações mais à direita e mais à esquerda
    4. Árvores de análise sintática
    5. Ambigüidade de GLC
    6. Simplificação de GLC
    7. Equivalência entre autômatos de pilha e GLC
  5. Análises léxica e sintática de linguagens de programação
  6. Linguagens recursivas e recursivamente enumeráveis
    1. Exemplo de problemas decidíveis relativos às linguagens estudadas
    2. Exemplos de problemas indecidíveis relativos às linguagens estudadas
  7. Problemas tratáveis e intratáveis
    1. Classes de problemas P, NP e NP-completo

Bibliografia

  1. INTRODUÇÃO À TEORIA DA COMPUTAÇÃO. MICHAEL SIPSER. 2a EDIÇÃO NORTE AMERICANA. THOMSON
  2. Linguagens Formais: Teoria, Modelagem e Implementação. Marcus Vinícius Midena Ramos, João José Neto, Ítalo Santiago Vega. Editora Bookman. 2009
  3. Compiladores : princípios e práticas. LOUDEN, Kenneth C. São Paulo: Thomson Pioneira, 2004.
  4. 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.
  5. Linguagens Formais e Autômatos. Paulo Blauth Menezes. Editora Sagra Luzzatto. Série Livros Didáticos – Instituto de Informática da UFRGS.
  6. 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.
  7. Machines, Languages and Computation. Peter J. Denning; Jack B. Dennis; Joseph E. Qualitz. Prentice-Hall. 1978.
  8. Compilers: Principles, Techniques, and Tools. Alfred V., Monica S. Lam, Ravi Sethi, Jeffrey D. Ullman. Addison Wesley; 2nd edition, 2008.