Aspectos formais

14298 palavras 58 páginas
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 Capítulo 2. Autômatos finitos determinísticos 1. Exercícios 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 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 Capítulo 5. Autômatos finitos não determinísticos 1 1 3 3 5 5 8 10 12 15 17 21 21 23 25 31 35 39 39 45 47 51 53 53 54 59 59 61 61 65

Capítulo 6. Operações com autômatos finitos 1. União 2. Concatenação 3. Estrela 4. Exercícios Capítulo 7. Autômatos de expressões regulares 1. Considerações gerais 2. União Capítulo 8. Gramáticas lineares à direita 1. Exercícios Capítulo 9. Linguagens livres de contexto 1. Gramáticas e linguagens livres de contexto 2. Linguagens sensíveis ao contexto v vi

SUMÁRIO

3. 4. 5.

Mais exemplos Combinando gramáticas Exercícios

66 69 72 75 75 77 80 83 84 88 90 93 93 94 98 102 103 103 105 111 113 118 123 123 126 128 130 132 137 139 139 143 143 145 147 150 151 152 155

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 Capítulo 11. Linguagens que não são livres de contexto 1. Introdução 2. Lema do bombeamento 3. Exemplos 4. Exercícios 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 Capítulo 13. Gramáticas e autômatos de pilha 1. O autômato de pilha de uma gramática 2. A receita e mais um exemplo 3. Provando a receita 4.

Relacionados

  • Cap1. aspectos formais
    17673 palavras | 71 páginas
  • Precisão de juizes nos aspectos formais do wzt
    4352 palavras | 18 páginas
  • Aspectos historicos e formais da teologia latino americana
    2848 palavras | 12 páginas
  • RESUMO Aspectos Formais Relativos A Acusac A O Ac A O Penal
    849 palavras | 4 páginas
  • Direito administrativo ASPECTOS DA ADMINISTRAÇÃO: SENTIDOS FORMAL - SUBJETIVO - ORGÂNICO
    315 palavras | 2 páginas
  • Aspectos da educação formal na colônia de pescadores da comunidade de redonda-icapuí-ceará
    1711 palavras | 7 páginas
  • Assinatura Digital x Assinatura Formal - Aspectos positivos e negativos e os Direitos da Personalidade
    5924 palavras | 24 páginas
  • Teste
    2223 palavras | 9 páginas
  • Trabalho Final de Graduação
    1592 palavras | 7 páginas
  • felippe
    1560 palavras | 7 páginas