LFA pumping lemma

Autômatos e Linguagens Formais

S. C. Coutinho
Universidade Federal do Rio de Janeiro

i

ii

c

by S. C. Coutinho 2007

Agradeço a
• David Boechat
• Gabriel Rosário pelas correções às notas de aula.

Sumário
Capítulo 1. Conjuntos e linguagens
1. Exercícios

1
1

Capítulo 2. Autômatos finitos determinísticos
1. Exercícios

3
3

Capítulo 3. Expressões regulares
1. Introdução
2. Lema de Arden
3. O algoritmo de substituição
4. Expressões regulares
5. Análise formal do algoritmo de substituição
6. Exercícios

5
5
8
10
12
15
17

Capítulo 4. Linguagens que não são regulares
1. Propriedade do bombeamento
2. Lema do bombeamento
3. Aplicações do lema do bombeamento
4. Exercícios

21
21
23
25
31

Capítulo 5.

35

Autômatos finitos não determinísticos

Capítulo 6. Operações com autômatos finitos
1. União
2. Concatenação
3. Estrela
4. Exercícios

39
39
45
47
51

Capítulo 7. Autômatos de expressões regulares
1. Considerações gerais
2. União

53
53
54

Capítulo 8. Gramáticas lineares à direita
1. Exercícios

59
59

Capítulo 9. Linguagens livres de contexto
1. Gramáticas e linguagens livres de contexto
2. Linguagens sensíveis ao contexto

61
61
65

v

vi

SUMÁRIO

3.
4.
5.

Mais exemplos
Combinando gramáticas
Exercícios

Capítulo 10. Árvores Gramaticais
1. Análise Sintática e línguas naturais
2. Árvores Gramaticais
3. Colhendo e derivando
4. Equivalência entre árvores e derivações
5. Ambigüidade
6. Removendo ambigüidade
7. Exercícios

66
69
72
75
75
77
80
83
84
88
90

Capítulo 11. Linguagens que não são livres de contexto
1. Introdução
2. Lema do bombeamento
3. Exemplos
4. Exercícios

93
93
94
98
102

Capítulo 12. Autômatos de Pilha
1. Heurística
2. Definição e exemplos
3. Computando e aceitando
4. Variações em um tema
5. Exercícios

103
103
105
111
113
118

Capítulo 13. Gramáticas e autômatos de pilha
1. O autômato