Linguagens Formais E Automatos
Casos: Linguagens Formais E Automatos. Pesquise 862.000+ trabalhos acadêmicosPor: Remilson • 29/9/2014 • 8.003 Palavras (33 Páginas) • 596 Visualizações
Linguagens Formais e Autômatos
Marcus Vinícius Midena Ramos
Curso de Engenharia de Computação
Universidade Federal do Vale do São Francisco
22 de abril de 2008
Sumário
1 Elementos de Matemática Discreta 5
1.1 Conjuntos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
1.2 Relações . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
1.3 Funções . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
1.4 Grafos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
1.5 Árvores . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
1.6 Teoremas e Demonstrações . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
1.7 Conjuntos Enumeráveis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
2 Conceitos Básicos de Linguagens 31
2.1 Símbolos e Cadeias . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
2.2 Linguagens . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
2.3 Gramáticas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45
2.4 Linguagens, Gramáticas e Conjuntos . . . . . . . . . . . . . . . . . . . . . . . . . 49
2.5 Reconhecedores . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50
2.6 Hierarquia de Chomsky . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61
3 Linguagens Regulares 67
3.1 Gramáticas Regulares . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67
3.2 Conjuntos e Expressões Regulares . . . . . . . . . . . . . . . . . . . . . . . . . . 72
3.3 Autômatos Finitos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 76
3.4 Equivalência entre Gramáticas Regulares e Conjuntos Regulares . . . . . . . . . 118
3.5 Equivalência entre Gramáticas Regulares e Autômatos Finitos . . . . . . . . . . . 129
3.6 Minimização de Autômatos Finitos . . . . . . . . . . . . . . . . . . . . . . . . . . 140
3.7 Transdutores Finitos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 153
3.8 Linguagens que não são Regulares . . . . . . . . . . . . . . . . . . . . . . . . . . 157
3.9 Propriedades de Fechamento . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 163
3.10 Questões Decidíveis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 172
4 Linguagens Livres de Contexto 181
4.1 Gramáticas Livres de Contexto . . . . . . . . . . . . . . . . . . . . . . . . . . . . 182
4.2 BNF Estendida . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 187
4.3 Árvores de Derivação . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 192
4.4 Ambigüidade . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 194
4.5 Simplificação de Gramáticas Livres de Contexto . . . . . . . . . . . . . . . . . . . 200
4.6 Formas Normais para Gramáticas Livres de Contexto . . . . . . . . . . . . . . . 211
4.7 Autômatos de Pilha . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 219
4.8 Equivalência entre Gramáticas Livres de Contexto e Autômatos de Pilha . . . . . 233
4.9 Relação entre Linguagens Livres de Contexto e Linguagens Regulares . . . . . . 245
4.10 Linguagens que não são Livres de Contexto . . . . . . . . . . . . . . . . . . . . . 246
4 Linguagens Formais - Teoria, Modelagem e Implementação
4.11 Linguagens Livres de Contexto Determinísticas . . . . . . . . . . . . . . . . . . . 253
4.12 Linguagens Livres de Contexto Não-Ambíguas . . . . . . . . . . . . . . . . . . . 259
4.13 Propriedades de Fechamento . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 262
4.14 Questões Decidíveis e Não-Decidíveis . . . . . . . . . . . . . . . . . . . . . . . . . 268
5 Linguagens Sensíveis ao Contexto 273
5.1 Gramáticas Sensíveis ao Contexto . . . . . . . . . . . . . . . . . . . . . . . . . . . 274
5.2 Gramáticas com Derivações Controladas . . . . . . . . . . . . . . . . . . . . . . . 279
5.3 Formas Normais para Gramáticas Sensíveis ao Contexto . . . . . . . . . . . . . . 285
5.4 Máquinas de Turing com Fita Limitada . . . . . . . . . . . . . . . . . . . . . . . 290
5.5 Equivalência entre Gramáticas Sensíveis ao Contexto e Máquinas de Turing com
Fita Limitada . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 297
5.6 Relação entre Linguagens Sensíveis ao Contexto e Linguagens Livres de Contexto 310
5.7 Linguagens que não são Sensíveis ao Contexto . . . . . . . . . . . . . . . . . . . . 311
5.8 Propriedades de Fechamento . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 316
5.9 Questões Decidíveis e Não-Decidíveis
...