A maior rede de estudos do Brasil

Grátis
271 pág.
Apostila LF

Pré-visualização | Página 1 de 49

Autômatos, Linguagens Formais e Computabilidade
S. C. Coutinho
&
Luis Menasché Schechter
Versão 0.85
Universidade Federal do Rio de Janeiro
c© by S. C. Coutinho & Luis Menasché Schechter, 2014
Agradecimentos
Agradecemos aos (ex-)alunos abaixo pelas sugestões, revisões e correções a
esta apostila.
• André Reis de Brito
• Carlos Eduardo da Silva Martins
• Christian da Silva Cabral Cardozo
• David Boechat
• Fabiano de Paula Martins
• Gabriel de Sá Rodrigues
• Gabriel Pires da Silva
• Gabriel Rosário
• Hugo Siqueira Gomes
• Igor Carpanese Figueiredo
• Igor da Fonseca Ramos
• Lenise Maria de Vasconcelos Rodrigues
• Pedro Carvalho da Silva
• Rodrigo Ming Zhou
• Ygor Luis Mesquita Pereira da Hora
• Yuri de Jesus Lopes Abreu
iii
Sumário
Agradecimentos iii
Capítulo 0. Introdução 1
1. Tópicos Centrais de Estudo 1
2. Conceitos Básicos 2
3. Operações sobre Linguagens 3
4. Exercícios 5
Parte 1. Linguagens Regulares 9
Capítulo 1. Linguagens Regulares e Autômatos Finitos Determinísticos 11
1. Autômatos Finitos Determinísticos (AFD’s) 11
2. Exercícios 15
Capítulo 2. Expressões Regulares 19
1. Breve Motivação 19
2. Expressões Regulares 20
3. Exercícios 25
Capítulo 3. Relação entre AFD’s e Expressões Regulares 27
1. Introdução 27
2. Lema de Arden 31
3. O Algoritmo de Substituição 34
4. Análise Formal do Algoritmo de Substituição 37
5. Último Exemplo 40
6. Exercícios 41
Capítulo 4. Autômatos Finitos Não-Determinísticos 45
v
vi SUMÁRIO
1. Autômatos Finitos Não-Determinísticos (AFND’s) 45
2. Algoritmo de Construção de Subconjuntos 52
3. Exercícios 59
Capítulo 5. Operações com Autômatos Finitos e Linguagens Regulares 61
1. Considerações Gerais 61
2. União 62
3. Concatenação 65
4. Estrela 67
5. Exemplo Mais Extenso 71
6. Propriedades de Fechamento das Linguagens Regulares 72
7. Exercícios 75
Capítulo 6. Lema do Bombeamento para Linguagens Regulares 79
1. Propriedade do Bombeamento 79
2. Lema do Bombeamento 82
3. Aplicações do Lema do Bombeamento 86
4. Exercícios 95
Capítulo 7. Gramáticas Regulares 99
1. Gramáticas 99
2. Gramáticas Regulares 101
3. Gramáticas Regulares e Autômatos Finitos 103
4. Exercícios 106
Parte 2. Linguagens Livres de Contexto 109
Capítulo 8. Linguagens Livres de Contexto e Gramáticas Livres de Contexto111
1. Gramáticas e Linguagens Livres de Contexto 111
2. Gramáticas que Não São Livres de Contexto 116
3. Mais Exemplos 117
4. Propriedades de Fechamento das Linguagens Livres de Contexto 121
5. Exercícios 127
SUMÁRIO vii
Capítulo 9. Árvores de Análise Sintática 131
1. Análise Sintática e Linguagens Naturais 131
2. Árvores de Análise Sintática 133
3. Colhendo e Derivando 137
4. Equivalência entre Árvores e Derivações 140
5. Ambiguidade 141
6. Removendo Ambiguidade 147
7. Exercícios 150
Capítulo 10. Lema do Bombeamento para Linguagens Livres de Contexto 151
1. Introdução 151
2. Lema do Bombeamento 153
3. Exemplos 157
4. Exercícios 162
Capítulo 11. Autômatos de Pilha 165
1. Heurística 165
2. Definição e Exemplos 168
3. Computando e Aceitando 174
4. Variações em um Tema 177
5. Exercícios 186
Capítulo 12. Relação entre Gramáticas Livres de Contexto e Autômatos de
Pilha 189
1. O Autômato de Pilha de uma Gramática 189
2. A Receita e Mais um Exemplo 192
3. Provando a Receita 196
4. Autômatos de Pilha Cordatos 198
5. A Gramática de um Autômato de Pilha 201
6. De Volta às Propriedades de Fechamento 207
7. Exercícios 208
viii SUMÁRIO
Parte 3. Computabilidade e Complexidade 211
Capítulo 13. Um Modelo Formal de Computação: A Máquina de Turing 213
1. A Máquina de Turing 213
2. Diagramas de Composição 226
3. Generalizações da Máquina de Turing 231
4. Propriedades de Fechamento das Linguagens Recursivas e
Recursivamente Enumeráveis 231
5. Exercícios 231
Capítulo 14. Poder e Limitações das Máquinas de Turing 235
1. Tese de Church-Turing 235
2. A Máquina de Turing Universal 237
3. O Problema da Parada 242
4. Exercícios 247
Capítulo 15. Introdução à Teoria da Complexidade 249
1. Complexidade de Tempo 249
2. Complexidade de Espaço (Memória) 252
3. Co-Classes 255
4. Redução Polinomial entre Linguagens 256
5. Exercícios 260
Referências Bibliográficas 263
CAPíTULO 0
Introdução
Neste capítulo, apresentamos os principais tópicos de estudo que serão tratados
ao longo destas notas e as principais motivações por trás deste estudo. Apresen-
tamos também os conceitos mais básicos relativos à linguagens formais que serão
utilizados no restante das notas.
1. Tópicos Centrais de Estudo
Os principais tópicos de estudo que serão cobertos ao longo destas notas são
descritos de forma bastante resumida abaixo.
I) Teoria da Computabilidade ou Teoria da Computação: Busca descrever
e estudar modelos matemáticos formais de computação, com o objetivo de
analisar as seguintes questões:
(1) Quais problemas podem ser algoritmicamente resolvidos por um compu-
tador?
(2) Quais são os limites do que um computador consegue resolver?
II) Teoria da Complexidade:
(1) Busca formas de avaliar formalmente o consumo de tempo e memória
dos algoritmos.
(2) Busca formas de determinar formalmente se existe um algoritmo eficiente
para resolver um dado problema.
III) Teoria de Autômatos: Busca o estudo de diferentes modelos formais de
computação, a partir de um modelo mais simples até o modelo mais poderoso,
que possui o mesmo poder de um computador real. Estes modelos compu-
tacionais são conhecidos como autômatos. Os modelos computacionais que
serão estudados nestas notas são, em ordem crescente de poder computacio-
nal, os seguintes:
1
2 0. INTRODUÇÃO
(1) Autômatos Finitos
(2) Autômatos de Pilha
(3) Máquinas de Turing
2. Conceitos Básicos
DEFINIÇÃO 0.1. Um alfabeto é um conjunto finito de símbolos Σ = {a1, . . . ,
an}.
DEFINIÇÃO 0.2. Uma palavra ou uma cadeia ou uma string em um alfabeto
Σ é uma sequência finita w = w1 . . . wn, n ∈ N, de símbolos de Σ (wi ∈ Σ, para
todo 1 ≤ i ≤ n). A palavra vazia, denotada por ε, é uma palavra que não contém
nenhum símbolo.
DEFINIÇÃO 0.3. O comprimento de uma palavra w, denotado por |w|, é defi-
nido como a quantidade de símbolos (não necessariamente distintos) que ocorrem
na palavra w. Então, se w = w1 . . . wn, |w| = n.
EXEMPLO 0.4. Seja Σ = {a, b}, w1 = baabb e w2 = aaa. Então, |w1| = 5 e
|w2| = 3.
OBSERVAÇÃO. Em qualquer alfabeto, é possível construir uma única palavra
de comprimento zero, também conhecida como palavra vazia, denotada por ε. Isto
é, |ε| = 0.
DEFINIÇÃO 0.5. Denotamos por Σ∗ o conjunto de todas as palavras forma-
das por símbolos no alfabeto Σ.
EXEMPLO 0.6. Seja Σ = {a, b}. Então, Σ∗ = {ε, a, b, aa, ab, ba, bb, aaa,
. . .}.
DEFINIÇÃO 0.7. Definimos uma linguagem formal, ou simplesmente lingua-
gem, L sobre um alfabeto Σ como sendo um subconjunto qualquer de Σ∗, isto é,
L ⊆ Σ∗.
3. OPERAÇÕES SOBRE LINGUAGENS 3
EXEMPLO 0.8. Seja Σ = {a, b}. Então, os conjuntos L1 = ∅, L2 = Σ∗,
L3 = {ε}, L4 = {a, bbb, aba} e L5 = {ε, a, aa, aaa, . . .} são todos exemplos de
linguagens sobre o alfabeto Σ, uma vez que todos estes conjuntos são subconjuntos
de Σ∗.
OBSERVAÇÃO. É importante observar que L1 e L3 são linguagens diferentes.
L1 é uma linguagem que não contém nenhuma palavra, isto é, é uma linguagem
vazia. Já L3 é uma linguagem que contém uma única palavra, sendo esta palavra a
palavra vazia.
EXEMPLO 0.9. Seja Σ = {A,B, . . . , Z, a, b, . . . , z}. Vamos denotar por
Lport o conjunto de todas as palavras da Língua Portuguesa. Vemos então que
Lport ⊆ Σ
∗
, logo Lport é efetivamente uma linguagem sobre o alfabeto Σ. Te-
mos que ε ∈ Σ∗, mas ε /∈ Lport; aula ∈ Σ∗ e aula ∈ Lport;

Crie agora seu perfil grátis para visualizar sem restrições.