Linguagens Formais E Automatos

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