Disciplina: DCC063 - LINGUAGENS FORMAIS E AUTÔMATOS
Horas Aula: 4
Departamento: DEPTO DE CIENCIA DA COMPUTACAO /ICE
Plano de Ensino
Voltar
Ementa
-Noções preliminares
-Linguagens regulares
-Gramáticas e linguagens livres de contexto
-Formas normais
-Autômatos e linguagens
-Autômatos com pilha e linguagens livres de contexto
-Hierarquia de Chomsky: classes de linguagens
Conteúdo
1) Noções preliminares
Teoria de conjuntos. Produto cartesiano, relações entre conjuntos, funções, relações de equivalência. Conjuntos enumeráveis e não enumeráveis. Definições recursivas. Indução matemática e diagonalização. Tipos de formalismos: grafos direcionados e lambda-cálculo.
2) Linguagens regulares
Definição de strings e linguagens. Especificação finita de linguagens. Conjuntos e expressões regulares.
3) Gramáticas e linguagens livres de contexto
Definições de linguagens livres de contexto. Derivação. Gramáticas regulares. Exemplos de gramáticas e linguagens: Pascal e expressões aritméticas. Estratégias de derivação: ambigüidade, derivações mais à esquerda e mais à direita, grafos de gramáticas, derivadores top-down, derivadores bottom-up.
4) Formas normais
Definição de formas normais e esquemas de restrição em gramáticas. Eliminação de: produções lambda, produções em cadeia, símbolos redundantes, recursão à esquerda. Forma normal de Chomsky e de Greibach
5) Autômatos e linguagens
Máquinas de estados finitos. Autômato finito determinista e não-determinista. Remoção de não-determinismo: fecho lambda. Minimização de autômatos finitos deterministas. Autômatos finitos e conjuntos regulares. O lema do bombeamento para linguagens regulares.
6) Autômatos com pilha e linguagens livres de contexto
Definições de autômato com pilha. Autômatos com pilha e linguagens livres de contexto. O lema do bombeamento para linguagens livres de contexto. Autômato com duas pilhas.
7) Hierarquia de Chomsky: classes de linguagens
Propriedades fechadas de linguagens regulares. Propriedades fechadas de linguagens livres de contexto. Tópicos para a próxima disciplina: Teoria de Linguagens.
Bibliografia
HOPCROFT, J. E. Introdução a teoria de autômatos, linguagens e computação. Rio de Janeiro: Elsevier. 560 p
LEWIS, H. R.; PAPADIMITRIOU, C. H. Elementos de teoria da computação. Porto Alegre: Bookman. 2000. 354 p.
SIPSER, M. Introdução à teoria da computação: Thomson Learning. 2007. 488 p.
Bibliografia(continuação)
Não informado
Bibliografia complementar
AHO, A. V.; LAM, M. S.; SETHI, R. Compiladores: Princípios, técnicas e ferramentas Rio de Janeiro: Pearson. 2007. 648 p.
COOPER, Keith D.; TORCZON, Linda. Construindo Compiladores. 2a Ed. Rio de Janeiro: Elsevier. 2014.
MENEZES, P. B. Linguagens formais e autômatos. Porto Alegre: Sagra Luzzatto. 2000. 170 p.
RAMOS, M. V. M.; NETO, J. J.; VEGA, Í. S. Linguagens formais: Teoria, modelagem e implementação. Porto Alegre: Bookman. 2009. 656 p.
ROSA, João Luis Garcia. Linguagens Formais e Autômatos. Rio de Janeiro: LTC Editora. 2010.
