Aspectos formais

Disponível somente no TrabalhosFeitos
  • Páginas : 58 (14298 palavras )
  • Download(s) : 0
  • Publicado : 14 de novembro de 2012
Ler documento completo
Amostra do texto
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 deArden 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 65Capí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.

Maisexemplos 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íciosCapí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.Autômatos de pilha cordatos 5. A gramática de um autômato de pilha 6. Exercícios Capítulo 14. Máquinas de Turing 1. Exercícios Capítulo 15. Máquinas de Turing e Linguagens 1. Conectando Máquinas em Paralelo 2. Fechamento de linguagens 3. A máquina de Turing universal 4. Comportamento de U 5. Linguagens não recursivas 6. O problema da parada Referências Bibliográficas

CAPíTULO 1

Conjuntos elinguagens

Neste primeiro capítulo, revisamos algumas propriedades básicas dos conjuntos e suas operações e introduzimos o conceito de linguagem formal. 1. Exercícios 1. Sejam A e B conjuntos, prove que: (a) ∅ ∪ A = A; (b) ∅ ∩ A = ∅; (c) se A ⊂ B então A ∩ B = A; (d) se A ⊂ B então A ∪ B = B; (e) A ∩ A = A = A ∪ A; (f) A ∪ B = B ∪ A e A ∩ B = B ∩ A; (g) A ∪ (B ∪ C) = (A ∪ B) ∪ C; (h) A ∩ (B ∩ C) = (A ∩B) ∩ C; (i) A ∪ (B ∩ C) = (A ∪ B) ∩ (A ∪ C); (j) A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C); (k) A \ B = A ∩ B onde B é o complemento de B no conjunto universo, isto é o conjunto que contém todos os conjuntos com que estamos trabalhando; (l) (A ∩ B) = A ∪ B; (m) (A ∪ B) = A ∩ B; (n) A = A; (o) A \ B = A \ (B ∩ A); (p) B ⊂ A se, e somente se, A ∩ B = ∅; (q) (A \ B) \ C = (A \ C) \ (B \ C) = A \ (B ∪ C); (r) A∩ B = ∅ e A ∩ B = ∅ se e somente se A = B. 2. Considere as afirmações abaixo: prove as verdaeiras e dê um contra-exemplo para as falsas. (a) se A ∪ B = A ∪ C então B = C;
1

2

1. CONJUNTOS E LINGUAGENS

(b) se A ∩ B = A ∩ C então B = C. 3. Sejam A, B e C conjuntos, prove que: (a) A × (B ∩ C) = (A × B) ∩ (A × C); (b) A × (B ∪ C) = (A × B) ∪ (A × C); (c) A × (B \ C) = (A × B) \ (A × C); 4.Explique a diferença entre ∅ e { }. Calcule L · ∅, onde L é uma linguagem qualquer. 5. Seja w uma palavra em um alfabeto Σ. Definimos o reflexo de w recursivamente da seguinte maneira: R = e se w = ax então wR = xR a onde a ∈ Σ. (a) Determine (turing)R e (anilina)R . (b) Se x e y são palavras no alfabeto Σ, determine (xy)R em função de xR e yR . (c) Determine (xR )R . 6. Sejam L1 e L2 linguagens...
tracking img