Apostila LFA
137799 palavras
552 páginas
Linguagens Formais e AutômatosMarcus 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
1.1 Conjuntos . . . . . . . . . . . .
1.2 Relações . . . . . . . . . . . . .
1.3 Funções . . . . . . . . . . . . .
1.4 Grafos . . . . . . . . . . . . . .
1.5 Árvores . . . . . . . . . . . . .
1.6 Teoremas e Demonstrações . .
1.7 Conjuntos Enumeráveis . . . .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
5
5
10
12
17
20
22
25
2 Conceitos Básicos de Linguagens
2.1 Símbolos e Cadeias . . . . . . . . . .
2.2 Linguagens . . . . . . . . . . . . . .
2.3 Gramáticas . . . . . . . . . . . . . .
2.4 Linguagens, Gramáticas e Conjuntos
2.5 Reconhecedores . . . . . . . . . . . .
2.6 Hierarquia de Chomsky . . . . . . .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
31
31
33
45
49
50
61
3 Linguagens Regulares
3.1 Gramáticas Regulares . . . . . . . . . . . . . . . . . . . . . . . .
3.2 Conjuntos e Expressões Regulares . . . . . . . . . . . . . . . . .
3.3 Autômatos Finitos . . . . . . . . . . . . . . . . . . . . . . . . . .
3.4 Equivalência entre Gramáticas Regulares e Conjuntos Regulares
3.5 Equivalência entre Gramáticas Regulares e Autômatos Finitos . .
3.6 Minimização de Autômatos Finitos . . . . . . . . . . . . . . . . .
3.7 Transdutores Finitos . . . . . . . .