Linguagens formais e autômatos
116802 palavras
468 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 31 31 33 45 49 50 61 67 67 72 76 118 129 140 153 157 163 172 181 182 187 192 194 200 211 219 233 245 246
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 . . . . . . .
3 Linguagens Regulares 3.1 Gramáticas Regulares .