LivroTeoria

Prévia do material em texto

Introdu�
~ao �a Teoria da Computa�
~ao:
Linguagens Formais e Computabilidade
Benedito Melo A
i�oly
Departamento de Cie^n
ias Exatas - DCE
Universidade Estadual do Sudoeste da Bahia - UESB
bma�uesb.br
Benjam��n Ren�e Callejas Bedregal
Laborat�orio de L�ogi
a e Intelige^n
ia Computa
ional - LabLIC
Departamento de Inform�ati
a e Matem�ati
a Apli
ada - DIMAp
Universidade Federal do Rio Grande do Norte - UFRN
bedregal�dimap.ufrn.br
Junho, 2000
Conte�udo
1 Introdu�
~ao 1
1.1 Con
eitos Matem�ati
os B�asi
os . . . . . . . . . . . . . . . . . . . . . . . . 3
1.1.1 Conjuntos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.1.2 Fun�
~oes e Rela�
~oes . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
1.1.3 Grafos e
�
Arvores . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
1.2 No�
~oes de Linguagens, Gram�ati
as e Auto^matos . . . . . . . . . . . . . . . 8
1.2.1 Linguagens Formais . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
1.2.2 Gram�ati
as . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
1.2.3 Auto^matos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
2 Auto^matos Finitos 19
2.1 Auto^matos Finitos Determin��sti
os . . . . . . . . . . . . . . . . . . . . . . 19
2.2 Linguagens e afd's . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
2.3 Linguagens Regulares . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
2.4 Auto^matos Finitos N~ao Determin��sti
os . . . . . . . . . . . . . . . . . . . . 27
2.5 Equivale^n
ia entre afd's e afn's . . . . . . . . . . . . . . . . . . . . . . . . 32
2.6 Exer
��
ios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41
3 Express~oes e Gram�ati
as Regulares 45
3.1 Express~oes Regulares . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45
3.2 Conex~ao entre Express~oes Regulares e Linguagens Regulares . . . . . . . . 49
3.2.1 Linguagens Regulares para Express~oes Regulares . . . . . . . . . . 52
3.3 Gram�ati
as Regulares . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56
3.3.1 Gram�ati
as Lineares �a Direita geram Linguages Regulares . . . . . 59
3.3.2 Linguagens Regulares para Gram�ati
as Lineares �a Direita . . . . . . 61
i
CONTE
�
UDO
3.3.3 Equivale^n
ia entre Linguagens Regulares e Gram�ati
as Regulares . 62
3.4 Propriedades das Linguagens Regulares . . . . . . . . . . . . . . . . . . . . 64
3.4.1 Quest~oes Elementares so^bre Linguagens Regulares . . . . . . . . . . 68
3.4.2 Identi�
ando Linguagens n~ao regulares . . . . . . . . . . . . . . . . 70
3.5 Exer
��
ios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73
4 Linguagens Livres de Contexto 79
4.1 Gram�ati
as Livres de Contexto . . . . . . . . . . . . . . . . . . . . . . . . 79
4.1.1 Deriva�
~oes mais �a esquerda e mais �a direita . . . . . . . . . . . . . 81
4.1.2
�
Arvores de deriva�
~ao . . . . . . . . . . . . . . . . . . . . . . . . . . 82
4.1.3 Rela�
~ao entre formas senten
iais e �arvores de deriva�
~ao . . . . . . . 84
4.2 An�alise e Ambiguidade . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 85
4.2.1 An�alise e pertine^n
ia . . . . . . . . . . . . . . . . . . . . . . . . . . 85
4.3 Gram�ati
as Livres de Contexto e Linguagens de Programa�
~ao . . . . . . . 90
4.4 Ambiguidades em gram�ati
as e linguagens . . . . . . . . . . . . . . . . . . 91
4.5 Simpli�
a�
~oes de Gram�ati
as Livres de Contexto . . . . . . . . . . . . . . . 94
4.5.1 Regra Geral de Substitui�
~ao . . . . . . . . . . . . . . . . . . . . . . 95
4.5.2 Remo�
~ao de Produ�
~oes Esquerda-Re
ursivas . . . . . . . . . . . . . 97
4.5.3 Remo�
~ao de Produ�
~oes In�uteis . . . . . . . . . . . . . . . . . . . . . 98
4.5.4 Remo�
~ao de �-produ�
~oes . . . . . . . . . . . . . . . . . . . . . . . . 102
4.5.5 Remo�
~ao de produ�
~oes unit�arias . . . . . . . . . . . . . . . . . . . . 104
4.6 Formas Normais . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 106
4.6.1 Forma Normal de Chomsky . . . . . . . . . . . . . . . . . . . . . . 106
4.6.2 Forma Normal de Greiba
h . . . . . . . . . . . . . . . . . . . . . . 108
4.7 Exer
��
ios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 111
5 Auto^matos a Pilha 115
5.1 Auto^mato a Pilha N~ao-Determin��sti
o (apn) . . . . . . . . . . . . . . . . . 115
5.1.1 A Linguagem A
eita por um Auto^mato a Pilha . . . . . . . . . . . 119
5.2 Auto^matos a Pilha e Linguagens Livre de Contexto . . . . . . . . . . . . . 122
5.2.1 Linguagens Livre de Contexto para Auto^matos a Pilha . . . . . . . 122
5.3 Auto^matos a Pilha para Gram�ati
as Livre de Contexto . . . . . . . . . . . 126
5.4 Exer
��
ios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 130
ii
Introdu�
~ao �a Teoria da Computa�
~ao:
Linguagens Formais e Computabilidade
CONTE
�
UDO
6 Propriedades das Linguagens Livres de Contexto 133
6.1 Lemas da Bomba . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 133
6.1.1 O Lema da Bomba para Linguagens Livres de Contexto . . . . . . . 133
6.2 Propriedades de Fe
ho e Algoritmos de De
is~ao para Linguagens Livres de
Contexto . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 135
6.2.1 Fe
ho de Linguagens Livres de Contexto . . . . . . . . . . . . . . . 136
6.2.2 Algumas Propriedades De
id��veis de Linguagens Livre de Contexto 136
6.3 Exer
��
ios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 138
7 M�aquinas de Turing 139
7.1 A M�aquina de Turing Padr~ao . . . . . . . . . . . . . . . . . . . . . . . . . 140
7.1.1 De�ni�
~ao de M�aquina de Turing . . . . . . . . . . . . . . . . . . . . 140
7.1.2 M�aquinas de Turing 
omo Re
onhe
edoras de Linguagens . . . . . . 146
7.1.3 M�aquinas de Turing 
omo Tradutores (Computadores) . . . . . . . 149
7.2 Combina�
~ao de M�aquinas de Turing para Realizar Tarefas Compli
adas . . 153
7.2.1 Diagramas de Blo
os . . . . . . . . . . . . . . . . . . . . . . . . . . 153
7.2.2 Ma
roinstru�
~ao . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 155
7.2.3 Subprogramas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 156
7.3 Tese de Turing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 158
7.4 Ligeiras Varia�
~oes da M�aquina de Turing Padr~ao . . . . . . . . . . . . . . . 161
7.4.1 M�aquinas de Turing 
om uma Op�
~ao de Permane^n
ia . . . . . . . . 162
7.4.2 M�aquinas de Turing 
om uma Fita Semi-in�nita . . . . . . . . . . . 162
7.4.3 M�aquinas de Turing O�-line . . . . . . . . . . . . . . . . . . . . . . 163
7.4.4 M�aquinas de Turing 
om M�ultiplas Fitas . . . . . . . . . . . . . . . 163
7.4.5 M�aquinas de Turing Multidimensional . . . . . . . . . . . . . . . . 164
7.4.6 M�aquinas de Turing N~ao determin��sti
as . . . . . . . . . . . . . . . 165
7.5 M�aquina de Turing Universal . . . . . . . . . . . . . . . . . . . . . . . . . 166
7.6 Exer
��
ios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 170
Introdu�
~ao �a Teoria da Computa�
~ao:
Linguagens Formais e Computabilidade
iii
CONTE
�
UDO
8 Hierarquia das Linguagens Formais 175
8.1 Linguagens re
ursivas e re
ursivamente enumer�aveis . . . . . . . . . . . . . 176
8.2 Linguagens que N~ao s~ao Re
ursivamente Enumer�aveis . . . . . . . . . . . . 178
8.3 Gram�ati
as Irrestritas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 181
8.4 Linguagens Sens��veis ao Contexto . . . . . . . . . . . . . . . . . . . . . . . 186
8.4.1 Gram�ati
as Sens��veis ao Contexto . . . . . . . . . . . . . . . . . . . 186
8.4.2 Auto^matos Limitados Linearmente. . . . . . . . . . . . . . . . . . 190
8.4.3 Rela�
~ao entre linguagens re
ursivas e linguagens sens��veis ao 
on-
texto . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 193
8.4.4 Equivale^n
ia entre ALL's e gram�ati
as sens��veis ao 
ontexto . . . . 195
8.4.5 Propriedades de fe
ho das linguagens sens��veis ao 
ontexto . . . . . 196
8.5 A Hierarquia de Chomsky . . . . . . . . . . . . . . . . . . . . . . . . . . . 197
8.6 Complexidade Computa
ional . . . . . . . . . . . . . . . . . . . . . . . . . 200
8.6.1 Medida e Complexidade . . . . . . . . . . . . . . . . . . . . . . . . 200
8.6.2 Fam��lias e Classes de Complexidade . . . . . . . . . . . . . . . . . . 202
8.6.3 Classi�
a�
~ao da Complexidade e a Hierarquia de Chomsky . . . . . 205
8.6.4 A Classe de Complexidade P e NP . . . . . . . . . . . . . . . . . . 206
8.7 Exer
��
ios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 209
9 Limites da Computa�
~ao Algor��tmi
a: Problemas Inde
id��veis 211
9.1 Alguns Problemas que N~ao Podem Ser Resolvidos por M�aquinas de Turing 211
9.2 O Problema da Parada para M�aquinas de Turing . . . . . . . . . . . . . . 213
9.3 Redu�
~ao de um Problema Inde
id��vel ao Problema da Parada . . . . . . . 217
9.4 Problemas Inde
id��veis para Linguagens Re
ursivamente Enumer�aveis . . . 220
9.5 O Problema da Corresponde^n
ia de Post . . . . . . . . . . . . . . . . . . . 222
9.6 Problemas Inde
id��veis para Linguagens Livres de Contexto . . . . . . . . 228
9.7 Exer
��
ios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 231
iv
Introdu�
~ao �a Teoria da Computa�
~ao:
Linguagens Formais e Computabilidade
Lista de Figuras
1.1 O diagrama de um grafo . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
1.2 Exemplo de �arvore . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
1.3 Representa�
~ao esquem�ati
a de um auto^mato. . . . . . . . . . . . . . . . . 17
2.1 Exemplo de afd. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
2.2 Exemplo de afd. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
2.3 representa�
~ao por tabela da afd do exemplo. . . . . . . . . . . . . . . . . 23
2.4 Exemplo de afd. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
2.5 Exemplo de afd. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
2.6 Exemplo de afd. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
2.7 Exemplo de afd. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
2.8 Exemplo de afd. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
2.9 Exemplo de afn. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
2.10 Exemplo de afn. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
2.11 Exemplo de um afn 
om �-transi�
~oes. . . . . . . . . . . . . . . . . . . . . 29
2.12 Exemplo de um afn 
om �-transi�
~oes. . . . . . . . . . . . . . . . . . . . . 30
2.13 afd equivalente ao afn do exemplo 2.4.4. . . . . . . . . . . . . . . . . . . 32
2.14 afd equivalente �a afn da �gura 2.10 . . . . . . . . . . . . . . . . . . . . . 33
2.15 Exemplo de afn. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
2.16 afd equivalente ao afn da �gura 2.15. . . . . . . . . . . . . . . . . . . . . 35
2.17 Exemplo de afn. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
2.18 afd equivalente ao afn da �gura 2.17. . . . . . . . . . . . . . . . . . . . . 38
2.19 Exemplo de afn. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
2.20 afd equivalente ao afn da �gura 2.19. . . . . . . . . . . . . . . . . . . . . 40
3.1 afn's que a
eitam as linguagens regulares ;, f�g e fag, respe
tivamente. . . 50
v
LISTA DE FIGURAS
3.2 Representa�
~ao esquem�ati
a de um afn que re
onhe
e L(r). . . . . . . . . . 51
3.3 Auto^mato para L(r
1
+ r
2
). . . . . . . . . . . . . . . . . . . . . . . . . . . . 51
3.4 Auto^mato para L(r
1
r
2
). . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51
3.5 Auto^mato para L(r
�
1
). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51
3.6 M
1
re
onhe
e L(aa) e M
2
re
onhe
e L(bb). . . . . . . . . . . . . . . . . . . 53
3.7 M
3
re
onhe
e L(aa + bb). . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53
3.8 M
4
re
onhe
e L((aa + bb)
�
). . . . . . . . . . . . . . . . . . . . . . . . . . . 53
3.9 M
5
re
onhe
e L(ba). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53
3.10 M
6
re
onhe
e L((aa + bb)
�
ba). . . . . . . . . . . . . . . . . . . . . . . . . . 54
3.11 afd para o exemplo 3.2.4. . . . . . . . . . . . . . . . . . . . . . . . . . . . 55
3.12 Representam V
i
�! a
1
a
2
: : : a
m
V
j
e V
i
�! a
1
a
2
: : : a
m
, respe
tivamente. . 60
3.13 afn resultante de uma gram�ati
a linear �a direita. . . . . . . . . . . . . . . . 61
3.14 afd M
2
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66
3.15 afd M
2
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66
4.1 Parte da �arvore de deriva�
~ao para a produ�
~ao A �! abAB
. . . . . . . . . 83
4.2 Uma �arvore de deriva�
~ao par
ial. . . . . . . . . . . . . . . . . . . . . . . . 84
4.3 Uma �arvore de deriva�
~ao. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 84
4.4 Exemplo de �arvores de deriva�
~ao diferentes para uma mesma 
adeia. . . . 92
4.5 Exemplo de �arvores de deriva�
~ao diferentes para uma mesma 
adeia. . . . 92
4.6 Exemplo de �arvore de deriva�
~ao numa gram�ati
a, n~ao ambigua, equivalente
�a gram�ati
a ambigua do exemplo anterior. . . . . . . . . . . . . . . . . . . 93
4.7 Exemplo de grafo de depende^n
ia . . . . . . . . . . . . . . . . . . . . . . . 100
4.8
�
Arvore de deriva�
~ao par
ial . . . . . . . . . . . . . . . . . . . . . . . . . . 101
4.9 Exemplo de grafo de depende^n
ia para remo�
~ao de produ�
~oes unit�arias. . . 105
5.1 Representa�
~ao esquem�ati
a de um auto^mato a pilha. . . . . . . . . . . . . 116
7.1 Representa�
~ao esquem�ati
a de uma m�aquina de Turing . . . . . . . . . . . 140
7.2 A situa�
~ao (a) antes do movimento e (b) ap�os. . . . . . . . . . . . . . . . 141
7.3 Parte da exe
u�
~ao de uma m�aquina de Turing. . . . . . . . . . . . . . . . 142
7.4 Con�gura�
~ao arbitr�aria de uma m�aquina de Turing . . . . . . . . . . . . . 144
7.5 Exemplo de 
ombina�
~ao de m�aquinas de Turing . . . . . . . . . . . . . . . 154
vi
Introdu�
~ao �a Teoria da Computa�
~ao:
Linguagens Formais e Computabilidade
LISTA DE FIGURAS
7.6 Divis~ao da �ta para simula�
~ao de subprogramas em m�aquinas de Turing. . 157
7.7 Conte�udo da �ta para a multipli
a�
~ao usando a id�eia de subprograma. . . 157
7.8 Fita ilimitada somente �a direita. . . . . . . . . . . . . . . . . . . . . . . . 162
7.9 Representa�
~ao esquem�ati
a de uma m�aquina de Turing o�-line. . . . . . . 163
7.10 Representa�
~ao esquem�ati
a de uma m�aquina de Turing 
om duas �tas. . . 164
7.11 Esquema de endere�
o bidimensional. . . . . . . . . . . . . . . . . . . . . . 164
7.12 Representa�
~ao esquem�ati
a de uma m�aquina de Turing universal. . . . . . 167
8.1 pro
edimento de enumera�
~ao das 
omputa�
~oes de uma m�aquina de Turing
M . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 177
8.2 Hierarquia de Chomsky original. . . . . . . . . . . . . . . . . . . . . . . . 198
8.3 Hierarquia de Chomsky. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 199
8.4 Con�gura�
~ao de uma M�aquina de Turing de duas �tas quere
onhe
e a
linguagem a
n
b
n
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 202
9.1 Diagrama de blo
os para uma suposta m�aquina de Turing que resolve o
problema da parada. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 214
9.2 Diagrama de blo
os para uma variante da suposta m�aquina de Turing que
resolve o problema da parada . . . . . . . . . . . . . . . . . . . . . . . . . 215
9.3 Algoritmo para o problema da parada usando um algoritmo de parada para
a �ta em bran
o. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 218
9.4 Algoritmo para o problema da parada 
om a �ta em bran
o baseado num
algoritmo para 
omputar f(n). . . . . . . . . . . . . . . . . . . . . . . . . . 219
9.5 Algoritmo de pertine^n
ia para linguagens re
ursivamente enumer�aveis. . . . 221
9.6 Uma solu�
~ao para o problema da parada baseada num algoritmo que diz
se uma linguagem �e �nita ou n~ao. . . . . . . . . . . . . . . . . . . . . . . 221
9.7 Exemplo de solu�
~ao-CP . . . . . . . . . . . . . . . . . . . . . . . . . . . . 223
9.8 Exemplo de solu�
~ao-CPM (par
ial) . . . . . . . . . . . . . . . . . . . . . . 225
9.9 Exemplo de solu�
~ao-CPM (
ontinua�
~ao) . . . . . . . . . . . . . . . . . . . 226
9.10 Algoritmo de pertine^n
ia para uma gram�ati
a irrestrita. . . . . . . . . . . 226
9.11 Algoritmo CPM. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 228
9.12 Algoritmo CP. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 230
Introdu�
~ao �a Teoria da Computa�
~ao:
Linguagens Formais e Computabilidade
vii
Dedi
at�oria do segundo autor
Com tudo meu amor, admira�
~ao
e 
arinho a minha m~ae,
que 
om sua for�
a e f�e,
nos legou um exemplo de vida.
Agrade
imentos
Durante v�arios anos, os autores (e alguns 
olegas) usaram vers~oes pr�evias deste texto
omo livro base para le
ionar as dis
iplinas de \Teoria da Computa�
ao" e \Linguagens
Formais", nas universidades: Universidade Federal de Pernambu
o, Universidade Federal
do Rio Grande do Norte e Universidade Estadual do Sudoeste da Bahia. Agrade
emos sin-
eramente aos alunos dessas turmas, pois 
om suas d�uvidas e questionamentos ajudaram
a re�nar este texto at�e 
hegar �a atual vers~ao.
Nossos agrade
imentos ao 
orpo do
ente do DIMAp-UFRN e da DCE-UESB pelo seu
onstante in
entivo para publi
ar esta obra.
Finalmente, agrade
emos parti
ularmente aos nossos 
olegas Regivan Hugo Nunes
Santiago, Wilson Rosa de Oliveira e Aar~ao Lyra pelo seus 
oment�arios e 
orre�
~oes do
texto.
ix
Cap��tulo 1
Introdu�
~ao
A importa^n
ia da teoria para a pr�ati
a, em qualquer 
ie^n
ia, seja fa
tual ou exata, �e
imensa. Para elu
idar a 
orrela�
~ao entre ambos aspe
tos de uma 
ie^n
ia foram formu-
ladas algumas frases 
onsagradas tais 
omo: \A teoria �e a luz da pr�ati
a" e \A pr�ati
a
sem a teoria �e 
ega, mas a teoria sem a pr�ati
a �e esteril". Como �e de supor, a 
ie^n
ia
da 
omputa�
~ao, n~ao poderia �
ar alheia a esta intera�
~ao e, portanto, uma teoria para
esta 
ie^n
ia se faz ne
ess�ario para \iluminar o 
aminho" dos 
ientistas da 
omputa�
~ao
(pr�ati
os), dos engenheiros em 
omputa�
~ao, dos analistas de sistemas, em �m de todos os
professionais que usem a 
omputa�
~ao 
omo objeto de estudo ou de trabalho. Assim, antes
de des
rever o que seria uma teoria para a 
ie^n
ia da 
omputa�
~ao, devemos ex
lare
er
que entendemos por 
ie^n
ia da 
omputa�
~ao ou, simplesmente, por 
omputa�
~ao.
Entendendo por 
omputa�
~ao tudo o que um 
omputador pode realizar, devemos pri-
meiro entender o que um 
omputador �e, 
uja resposta poderia ser dada em termos de
hardware e te
nologia. Mas, temos de ter 
uidado, para n~ao nos limitarnos �a te
nologia
do momento, pois nessa de�ni�
~ao de 
omputador devem 
oexistir os primeiros 
omputado-
res, 
al
uladoras, super 
omputadores e futuros 
omputadores. Ou seja, seria ne
ess�ario
uni�
ar 
ara
ter��sti
as essen
iais e 
omuns a todos os 
omputadores, de tal modo a dis-
tinguir um 
omputador de outros tipos de hardware, tais 
omo elevadores, to
a CD, et
.
Isto nos levar�a, irremediavelmente, a de�nir uma no�
~ao abstrata de 
omputador, onde ele
possa ser melhor des
rito em termos do que ele faz.
A teoria nos forne
e 
on
eitos e prin
��pios para nos ajudar entender a natureza geral
da 
ie^n
ia do 
omputador. O 
ampo dessa dis
iplina in
lui um vasto leque de t�opi
os es-
pe
iais, desde projetos de m�aquinas at�e programa�
~ao. O uso dos 
omputadores no mundo
real envolve uma riqueza de detalhes espe
���
os que devem ser aprendidos para uma apli-
a�
~ao 
om su
esso. Isto faz 
om que a 
ie^n
ia da 
omputa�
~ao seja diversi�
ada e ampla.
Apesar dessa diversidade, existem alguns prin
��pios b�asi
os 
omuns. Para estudar esses
prin
��pios b�asi
os, 
onstruiremos modelos abstratos de 
omputadores e 
omputa�
~ao. Esses
modelos 
ont�em as 
ara
ter��sti
as importantes que s~ao 
omuns tanto ao hardware quanto
ao software, essen
iais a muitos 
onstrutos espe
iais e 
omplexos en
ontrados quando se
trabalha 
om 
omputadores. Mesmo que esses modelos sejam muito simples para serem
1
Cap��tulo 1. Introdu�
~ao
apli
ados imediatamente nas situa�
~oes do mundo real, o entendimento que ganhamos em
estud�a-los nos forne
e fundamentos sobre os quais o desenvolvimento espe
���
o �e baseado.
Esta abordagem n~ao �e ex
lusividade da 
ie^n
ia da 
omputa�
~ao. A 
onstru�
~ao de mode-
los �e essen
ial em qualquer dis
iplina 
ient���
a, e a utilidade de uma dis
iplina depende
frequentemente da teoria e de leis simples, ainda que poderosas. Al�em do mais, as id�eias
que dis
utiremos te^m algumas apli
a�
~oes imediatas e importantes. Os 
ampos de projetos
digitais, linguagens de programa�
~ao e 
ompiladores s~ao os exemplos mais �obvios, existem
por�em muitos outros (Proto
olos de 
omuni
a�
~ao, projetos de hardwares digitais, et
.).
Este texto �e o resultado de diversos 
ursos ministrados pelos autores para a dis
ipli-
na de \teoria da 
omputa�
~ao" dos 
ursos de gradua�
~ao em Ba
harelado em Cie^n
ia da
Computa�
~ao da Universidade Federal do Rio Grande do Norte - UFRN, da Universida-
de Federal de Pernambu
o - UFPE e da Universidade Estadual do Sudoeste da Bahia -
UESB e no 
urso de Engenharia da Computa�
~ao da UFRN. Como esta dis
iplina �e pre-
requisito da dis
iplina \
ompiladores", enfatizamos os 
on
eitos de linguagens formais,
om suas abordagens atrav�es de auto^matos e de gram�ati
as. Mas, 
omo prin
ipalmente
�e um 
urso de \teoria da 
omputa�
~ao ", tamb�em estudamos a no�
~ao de 
omputabilidade
e 
onsideramos uma breve dis
us~ao de 
omplexidade 
omputa
ional.
Os t�opi
os apresentados neste texto s~ao importantes para os estudantes de inform�ati
a,
seja de 
ie^n
ias ou de engenharia, pois os 
olo
am diante de quest~oes profundas de na-
tureza 
omputa
ional e de 
onhe
imentos que n~ao ser~ao rapidamente absoletados, pois
n~ao dependem da te
nologia. Assim, este texto nos permite vislumbrar o poder das fer-
ramentas matem�ati
as e dos m�etodos formais para modelar feno^menos da 
omputa�
~ao.
No entanto, �e �obvio que este texto n~ao �e exaustivo no que tange �a teoria da 
omputa�
~ao,
pois s�o se dire
iona a modelar linguagens formais e 
omputabilidade 
l�assi
a, deixando de
lado 
ertos aspe
tos espe
���
os, 
omo por exemplo 
omputa�
~ao 
on
orrente e distrib��da,
espe
i�
a�
~ao formal, 
omputa�
~oes num�eri
as envolvendo n�umeros reais, et
.
�
E este estudo
dos feno^menos da 
omputa�
~ao atrav�es de modelos matem�atios ou formais �e que ergue a
omputa�
~ao ao patamar de uma 
ie^n
ia em lugar de uma mera te
nologia.
Neste texto, estudaremos diversas 
lasses de linguagens (formais), mas daremos e^nfase
espe
ialmente a quatro delas:
1. Linguagens regulares,
2. Linguagens livres de 
ontexto,
3. Linguagens sens��veis ao 
ontexto e
4. Linguagens re
ursivamente enumer�aveis.
Cada uma dessas 
lasses de linguagens ser�a abordada atrav�es de auto^matos, que s~ao
modelos matem�ati
os de 
lasses de 
omputadores digitais, e atrav�es de gram�ati
as, que
s~ao, basi
amente, um 
onjunto de regras que dizem 
omo 
onstruir palavras v�alidas da
linguagem.
2
Introdu�
~ao �a Teoria da Computa�
~ao:
Linguagens Formais e Computabilidade
Cap��tulo 1. Introdu�
~ao
Exploramos o mais 
omplexo destes auto^matos, e observamos que ele n~ao s�o tem
apa
idade para re
onhe
er linguagens formais, mas tamb�em pode transformar entradas
em sa��das, ou seja realizar 
omputa�
~oes 
omo qualquer 
omputador real faz. Este �e o
ponto de partida para se introduzir a no�
~ao de 
omputabilidade e estabele
er os limites
do mundo da 
omputa�
~ao.
Finalmente, 
om um 
onhe
imento do que �e e o que n~ao �e 
omput�avel, podemos nos
preo
upar 
om analizar a qualidade das solu�
~oes, isto �e, n~ao s�o �e importante saber se
um determinado problema admite uma solu�
~ao implement�avel num 
omputador, mas se
essa solu�
~ao vai nos ser �util (se vai ser realizada em um tempo razo�avel, ou ainda se ela
o
upa espa�
o de mem�oria que dispomos). Ou seja, agora podemos nos preo
upar 
om a
omplexidade 
omputa
ional das solu�
~oes. Para isso, introduzimos algumas medidas de
omplexidade baseadas no tempo de exe
u�
~ao de um algoritmo e do espa�
o usado por ele.
Neste 
ap��tulo, veremos alguns 
on
eitos matem�ati
os b�asi
o, fundamentais para o
entendimento do texto. Al�em do mais, veremos de modo geral e super�
ial as tre^s vis~oes
(linguagem, auto^mato e gram�ati
a) que adotaremos neste texto, para estudar o poder
omputa
ional dos nossos modelos.
1.1 Con
eitos Matem�ati
os B�asi
os
1.1.1 Conjuntos
Um 
onjunto �e uma 
ole�
~ao de objetos (seus elementos) distintos. Des
revemos um 
on-
junto enumerando um a um seus elementos em alguma ordem adequada ou des
revendo
uma propriedade que s�o os elementos do 
onjunto possuem ou satisfazem. Em geral, deno-
tamos 
onjuntos por letras mai�us
ulas 
om ou sem ��ndi
es, por exemplo A;B;C;A
1
; B
k
;
et
. Se a �e um elemento de um 
onjunto A, dizemos que a perten
e a A, denotado por
a 2 A. Se v�arios elementos, digamos a; b e 
 perten
em ao 
onjunto A denotamo-lo por
a; b; 
 2 A.
O 
onjunto que n~ao tem elementos �e denominado 
onjunto vazio, denotado por
;. O 
onjunto vazio pode ser espe
i�
ado por uma propriedade que nenhum elemento
satisfaz. Por exemplo, ; = fx=x 6= xg. O 
onjunto 
ujos elementos s~ao todos objetos
f��si
os ou mentais que existem, existiram ou existir~ao no universo �e denominado 
onjunto
universo e o denotamos por U.
Um 
onjunto A �e um sub
onjunto de um 
onjunto B ou A est�a 
ontido ou �e igual a
B, denotado por X � B, se todos os elementos de A s~ao elementos de B, isto �e, se para
todo x, se x 2 A ent~ao x 2 B. Os 
onjuntos A e B s~ao iguais, denotado por A = B,
se A � B e B � A. Dizemos que um 
onjunto A �e um sub
onjunto pr�oprio de B,
denotado por A � B, se A � B e A n~ao �e igual a B, ou seja se A � B e existe um
elemento de B que n~ao est�a em A.
Proposi�
~ao 1.1.1 Sejam A; B e C 
onjuntos qualquer. Ent~ao
Introdu�
~ao �a Teoria da Computa�
~ao:
Linguagens Formais e Computabilidade
3
1.1. Con
eitos Matem�ati
os B�asi
os
1. ; � A.
2. Se A � B ent~ao A � B.
3. Se A � B e B � C ent~ao A � C.
4. Se A � B e B � C ent~ao A � C.
5. Se A � B e B � C ent~ao A � C.
A seguir de�niremos algumas opera�
~oes b�asi
as so^bre 
onjuntos. Sejam A; B e C tre^s
onjuntos quaisquer.
� Uni~ao: A [B = fx = x 2 A ou x 2 Bg,
� Interse
�
~ao: A \B = fx = x 2 A e x 2 Bg,
� Diferen�
a: A� B = fx = x 2 A e x 62 Bg,
� Complementa�
~ao: A = fx = x 62 Ag.
Propriedades:
� A [ B = B [ A,
� A \ B = B \ A,
� A [ (B \ C) = (A \B) [ (A \ C),
� A \ (B [ C) = (A [B) \ (A [ C),
� A [ ; = A� ; = A,
� A \ ; = ;,
� ; = U,
� A = A,
� A [ B = A \ B,
� A \ B = A [ B,
� Se A � B ent~ao A [B = B, A \B = A e B � A.
4
Introdu�
~ao �a Teoria da Computa�
~ao:
Linguagens Formais e Computabilidade
Cap��tulo 1. Introdu�
~ao
Se A e B s~ao 
onjuntos sem nenhum elemento em 
omum, isto �e, se A\B = ;, ent~ao
A e B s~ao denominados 
onjuntos disjuntos.
Um 
onjunto diz-se �nito se 
ont�em um n�umero �nito de elementos. Caso 
ontr�ario,
e^le se diz in�nito. O tamanho ou 
ardinalidade de um 
onjunto �nito �e o n�umero de
elementos que e^le 
ont�em , denotado por jA j.
Seja fA
i
g
i2I
uma fam��lia de 
onjuntos indexada por I. Ent~ao
1. a uni~ao da fam��lia �e de�nida por
[
i2I
A
i
= fx = existe i 2 I tal que x 2 A
i
g
2. a interse�
~ao da fam��lia �e de�nida por
\
i2I
A
i
= fx = para todo i 2 I tal que x 2 A
i
g
3. se I = f1; 2; � � � ; ng ent~ao denotamos a uni~ao e interse�
~ao da fam��lia fA
i
g
i2I
por
n
[
i=1
A
i
e
n
\
i=1
A
i
Um dado 
onjunto pode ter muitos sub
onjuntos. O 
onjunto de todos os sub
onjuntos
de um 
onjunto A �e 
hamado o 
onjunto pote^n
ia ou 
onjunto das partes de A,
denotado por 2
A
ou
}
(A).
Exemplo 1.1.2 Se A �e o 
onjunto fa; b; 
g, ent~ao seu 
onjunto pote^n
ia �e
2
A
= f;; fag; fbg; f
g; fa; bg; fa; 
g; fb; 
g; fa; b; 
gg
Observe que neste 
aso j A j= 3 e j 2
A
j= 2
jAj
= 2
3
= 8. Generalizando, se A �e
um 
onjunto �nito ent~ao j 2
A
j= 2
jAj
. Esta propriedade deu origem ao nome de 
onjunto
pote^n
ia.
1.1.2 Fun�
~oes e Rela�
~oes
Uma fun�
~ao �e uma regra que asso
ia a 
ertos elementos de um 
onjunto um �uni
o ele-
mento de outro 
onjunto. Se f denota uma fun�
~ao, ent~ao o primeiro 
onjunto �e 
hamado
onjunto de partida e o segundo 
onjunto �e 
hamado 
onjunto de 
hegada. Es
re-
veremos f : A �! B, para indi
ar que f �e uma fun�
~ao 
ujo 
onjunto de partida �e A e
ujo 
onjunto de 
hegada �e B. Eventualmente, teremos 
asos em que alguns elementos
Introdu�
~ao �a Teoria da Computa�
~ao:
Linguagens Formais e Computabilidade
5
1.1. Con
eitos Matem�ati
os B�asi
os
do 
onjunto de partida n~ao tenham asso
iado nenhum elemento do 
onjunto de 
hegada
atrav�es da fun�
~ao f . O sub
onjunto de A 
ujos elementos s~ao asso
iados a elementos de B
�e 
hamado dom��nio de f , denotado por dom(f). Analogamente, o sub
onjunto de B, aos
quais aqueles elementos de A foram asso
iados, �e 
hamado imagem ou 
ontradom��nio
de f e o denotamos por img(f). Se o dom��nio de f �e todo A, f diz-se uma fun�
~ao total
sobre A, 
aso 
ontr�ario f diz-se uma fun�
~ao par
ial.
No 
otidiano sempre estamos rela
ionando objetos de um mesmo tipo ou de diferentes
tipos. Por exemplo, a rela�
~ao \perte
er �a mesma familia", rela
iona pessoas que s~ao de
uma mesma familia e a rela�
~ao \ser dono" rela
iona pessoas 
om objetos. Assim, uma
rela�
~ao exige que exista uma 
onex~ao entre as 
oisas que se rela
ionam. Esta no�
~ao de
onex~ao de um objeto a 
om um objeto b, pode ser formalmente 
olo
ado introduzindo
a no�
~ao de par ordenado, (a; b). A no�
~ao de par ordenado tem a seguinte propriedade
fundamental:
(x
1
; x
2
) = (y
1
; y
2
) se, e somente se, x
1
= y
1
e x
2
= y
2(1.1)
Ou seja nos pares ordenados a ordem em que s~ao dispostos os elementos �e importante.
Colo
ado dessa maneira, aparentemente, n~ao podemos pensar um par ordenado 
omo
um 
onjunto, mas poder��amos en
arar um par ordenado, (a; b), 
omo uma abrevia�
~ao
do 
onjunto fa; fa; bgg. Esta vis~ao 
onjuntista de par ordenado satisfaz a propriedade
fundamental 1.1. O 
onjunto de todos os pares ordenados poss��veis de ser 
onstru��dos
entre um 
onjunto A e um Conjunto B, �e denominado produto 
artesiano de A 
om
B, 
uja denota�
~ao �e A� B. Assim,
A� B = f(a; b) = a 2 A e b 2 Bg:
A no�
~ao de par ordenado pode ser estendida �a no�
~ao de n-tuplas ordenadas, isto �e,
em vez de 
onsiderar elementos de dois 
onjuntos, 
onsiderar elementos de n 
onjuntos.
Denotaremos uma n-tupla por (a
1
; � � � ; a
n
). Analogamente, podemos 
onsiderar o produto
artesiano dos 
onjuntos A
1
; � � � ; A
n
, denotado por A
1
� � � � � A
n
, por
A
1
� A
2
� � � � � A
n
= f(x
1
; x
2
; � � � ; x
n
) = x
i
2 A
i
; para 
ada 1 � i � ng
Assim, uma rela�
~ao r entre os elementos de um 
onjunto A 
om os elementos de um
onjunto B �e, em suma, um sub
onjunto do produto 
artesiano de A 
om B, ou seja,
r � A�B. Analogamente, uma fun�
~ao f : A �! B pode ser vista 
omo um sub
onjunto
do produto 
artesiano de A 
om B, isto �e, f � A � B, onde 
ada x
i
pode o
orrer no
m�aximo uma vez 
omo o primeiro elemento de um par ordenado em f . Esta maneira de
en
arar fun�
~oes �e 
hamada gr�a�
o da fun�
~ao f . Claramente, as rela�
~oes s~ao mais gerais
que as 
fun�
~oes: numa fun�
~ao 
ada elemento do dom��nio tem asso
iado a ele exatamente
um elemento no 
ontradom��nio; numa rela�
~ao podem existir v�arios de tais elementos no
ontradom��nio.
6
Introdu�
~ao �a Teoria da Computa�
~ao:
Linguagens Formais e Computabilidade
Cap��tulo 1. Introdu�
~ao
Uma rela�
~ao espe
ialmente importante �e uma rela�
~ao de equivale^n
ia, que �e uma
generaliza�
~ao do 
on
eito de igualdade (identidade). Para indi
ar que um par (x; y) �e
equivalente, es
revemos
x � y
Uma rela�
~ao, denotada por �, �e 
onsiderada uma equivale^n
ia se ela satisfaz tre^s
regras:
� Re
exividade: x � x para todo x,
� Simetria: se x � y, ent~ao y � x e
� Transitividade: se x � y e y � z, ent~ao x � z.
Exemplo 1.1.3 Seja N = f0; 1; 2; : : :g o 
onjunto dos n�umeros naturais e de�na
x � y se e somente se x (mod 3) = y (mod 3)
Assim, 2 � 5, 6 � 9 e 10 � 16. Isso �e 
laramente uma rela�
~ao de equivale^n
ia.
1.1.3 Grafos e
�
Arvores
Um grafo �e um 
onstruto 
onstitu��do de dois 
onjuntos �nitos, o 
onjunto V = fv
1
; v
2
; : : : ; v
n
g
de v�erti
es e o 
onjunto A = fa
1
; a
2
; : : : ; a
m
g de arestas. Cada aresta �e um par de
v�erti
es de V , por exemplo, e
i
= (v
j
; v
k
).
Neste 
aso, dizemos que a aresta e
i
�e uma aresta de sa��da para v
j
e de 
hegada
para v
k
. Tal 
onstruto �e mais pre
isamente um grafo dirigido, uma vez que asso
iamos
uma dire�
~ao (de v
j
a v
k
) a 
ada aresta. Grafos podem ser rotulados, sendo o r�otulo um
nome ou outra informa�
~ao asso
iada �as 
omponentes do grafo. Tanto os v�erti
es quanto
as arestas podem ser rotulados.
Uma maneira 
onveniente de se visualizar grafos �e atrav�es de diagramas, nos quais
os v�erti
es s~ao representados por 
��r
ulos e as arestas por linhas, 
om setas 
one
tando
os v�erti
es. O grafo 
om v�erti
es fv
1
; v
2
; v
3
g e arestas f(v
1
; v
3
); (v
3
; v
1
); (v
3
; v
2
); (v
3
; v
3
)g �e
desenhado na �gura 1.1.
Uma seque^n
ia de arestas (v
i
; v
j
); (v
j
; v
k
); (v
k
; v
l
); � � � ; (v
m
; v
n
) diz-se um 
aminho de
v
i
a v
n
. O 
omprimento de um 
aminho �e o n�umero total de arestas que ele atravessa
indo do v�erti
e ini
ial ao v�erti
e �nal. Um 
aminho no qual nenhuma aresta �e repetida
diz-se uma trilha. Uma trilha �e simples se nenhum v�erti
e �e repetido, isto �e, se n~ao
existem duas arestas distintas, (v
i
; v
j
) e (v
k
; v
l
), na trilha tal que v
i
= v
k
ou v
j
= v
l
. Uma
trilha de v
i
a ele pr�oprio diz-se um 
i
lo 
om base v
i
. Se nenhum v�erti
e al�em de v
i
, a
Introdu�
~ao �a Teoria da Computa�
~ao:
Linguagens Formais e Computabilidade
7
1.2. No�
~oes de Linguagens, Gram�ati
as e Auto^matos
v v v
1 2 3
Figura 1.1: O diagrama de um grafo
base, �e repetido o 
i
lo 
om base v
i
diz-se simples. No grafo da �gura 1.1 (v
1
; v
3
); (v
3
; v
2
)
�e uma trilha simples de v
1
a v
2
. A seque^n
ia de arestas (v
1
; v
3
); (v
3
; v
3
); (v
3
; v
1
) �e um 
i
lo
om base v
1
, mas n~ao simples, pois repete o v�erti
e v
3
, j�a a seque^n
ia (v
1
; v
3
); (v
3
; v
1
) �e
um 
i
lo simples 
om base v
1
. Se as arestas de um grafo s~ao rotuladas, podemos falar do
r�otulo de um 
aminho. Este r�otulo �e a seque^n
ia de r�otulos das arestas en
ontradas
quando se per
orre a trilha.
Em v�arias o
asi~oes, nos referiremos a um algoritmo para a
har todas as trilhas sim-
ples entre dois v�erti
es (ou todos os 
i
los simples baseados num v�erti
e). Se n~ao nos
preo
uparmos 
om e�
ie^n
ia podemos usar o seguinte m�etodo. Ini
iar do v�erti
e dado,
digamos v
i
, liste todas as arestas de sa��da de v
i
, (v
i
; v
k
); (v
i
; v
l
); : : :. Neste ponto temos
todas as trilhas de 
omprimento um, 
ome�
ando em v
i
. Para todos os v�erti
es v
k
; v
l
; : : :
al
an�
ados, liste todas as arestas de sa��da desde que elas n~ao levem a qualquer v�erti
e j�a
usado na trilha que estamos 
onstruindo. Ap�os isto, teremos todas as trilhas simples de
omprimento dois ini
iando em v
i
e assim por diante. Como s�o existe um n�umero �nito
de v�erti
es, mais 
edo ou mais tarde teremos listado todas as trilhas simples, 
om in��
io
em v
i
. Desses es
olheremos aqueles terminando no v�erti
e desejado.
As �arvores s~ao tipos parti
ulares de grafos. Uma �arvore �e um grafo dirigido que n~ao
possui 
i
los, tendo um v�erti
e distinguido 
hamado raiz, tal que existe exatamente uma
trilha da raiz a qualquer outro v�erti
e. Esta de�ni�
~ao impli
a que n~ao existe aresta de
hegada na raiz e que existe v�erti
es sem arestas de sa��da, 
hamados folhas da �arvore.
Se existe uma aresta de v
i
para v
j
, v
i
�e dita um pai de v
j
, e v
j
�e dito um �lho de v
i
.
O n��vel asso
iado a 
ada v�erti
e �e o n�umero de arestas na trilha da raiz ao v�erti
e. A
altura de uma �arvore �e o n�umero mais alto do n��vel de algum v�erti
e.
1.2 No�
~oes de Linguagens, Gram�ati
as e Auto^matos
Na primeira parte de nosso 
urso abordaremos tre^s ideias fundamentais: linguagem,
grama^ti
a e auto^mato. Estaremos parti
ularmente interessados nas suas rela�
~oes.
8
Introdu�
~ao �a Teoria da Computa�
~ao:
Linguagens Formais e Computabilidade
Cap��tulo 1. Introdu�
~ao
Raiz
Folha
Altura=3
Nivel 0
Nivel 3
Figura 1.2: Exemplo de �arvore
1.2.1 Linguagens Formais
Em Portugue^s, existem tre^s tipos de entidades diferentes: letras, palavras e senten�
as.
Existe um 
erto paralelismo entre elas, no sentido de que grupos de letras 
onstituem
uma palavra, e grupos de palavras uma senten�
a. Mas, nem toda 
on
atena�
~ao de letrasforma uma palavra, nem toda seque^n
ia de palavras uma senten�
a. A analogia pode ser
estendida a paragrafos, hist�orias, e assim por diante. A situa�
~ao, se d�a, tamb�em, para
as linguagens de programa�
~ao, na qual 
ertos agrupamentos de palavras 
haves s~ao um
omando e algumas seque^n
ias de 
omandos s~ao programas.
Para 
onstruir uma teoria geral que uni�que todos estes 
asos, ser�a ne
ess�ario adotar
uma de�ni�
~ao para a estrutura de linguagens mais universal, isto �e, uma estrutura na
qual a de
is~ao de quando uma 
adeia de unidades 
onstitui uma unidade maior v�alida,
seja baseada na apli
a�
~ao de regras expli
itamente de�nidas.
Em linguagens tipo Portugue^s, Ingle^s e em alguns dialetos tipo Guarany, Aymara,
et
. n~ao podemos dar regras que nos permitam des
rever todas as frases 
oerentes da
linguagem. Isto porque elas s~ao linguagens ditas naturais , na qual depende de nossa
habilidade para interpretar met�aforas po�eti
as de senten�
as mal es
ritas. Isto j�a n~ao
a
onte
e 
om linguagens de programa�
~ao, pois elas s~ao \formais", e o 
ompilador de uma
linguagem de programa�
~ao �e um pro
edimento que analiza a 
orretude de uma seque^n
ia
de s��mbolos e determina se ela 
onstitui um programa v�alido ou n~ao. Assim, o 
ompilador
n~ao pro
ura saber o que o programa faz, mas se ele est�a 
orretamente es
rito.
Neste texto, estudaremos alguns aspe
tos b�asi
os do que se 
onhe
e 
omo \teoria de
linguagens formais". A palavra \formal" nos diz que todas as regras para a linguagem
s~ao expli
itamente de
laradas em termos das 
adeias de s��mbolos que podem o
orrer nela.
Nenhuma liberdade �e tolerada e nenhum \entendimento profundo" �e pre
iso. Senten�
as
ser~ao 
onsideradas 
omo meros s��mbolos e n~ao 
omo express~oes de ideias na mente huma-
na. Neste modelo b�asi
o, as linguagens (formais) n~ao servem para a 
omuni
a�
~ao entre
Introdu�
~ao �a Teoria da Computa�
~ao:
Linguagens Formais e Computabilidade
9
1.2. No�
~oes de Linguagens, Gram�ati
as e Auto^matos
intele
tos, mas 
omo um jogo de s��mbolos, 
om regras formais. O termo \formal", aqui
usado, enfatiza que �e a forma da 
adeia de s��mbolos que nos interessa e n~ao seu signi�
ado.
Seja � um 
onjunto �nito n~ao vazio de s��mbolos, 
hamado alfabeto. Dos s��mbolos
individuais 
onstruiremos 
adeias (strings) que s~ao seque^n
ias �nitas de s��mbolos do
alfabeto.
Exemplo 1.2.1 Se o alfabeto fo^r � = fa; bg, ent~ao abab e aaabba s~ao 
adeiais sobre �.
Com raras ex
e�
~oes, usaremos as letras min�us
ulas ini
iais do alfabeto portugue^s,
omo a; b; 
; d e e para representar elementos de um alfabeto � e letras min�us
ulas do
�nal do alfabeto protugue^s, 
omo u; v; w; x; y e z, para indi
ar nomes de 
adeias.
Por exemplo, es
reveremos w = abaaa para indi
ar que a 
adeia de nome w tem o valor
espe
���
o abaaa.
A 
on
atena�
~ao de duas 
adeias w e v, denotado por wv, �e a 
adeia obtida juntando-
se os s��mbolos de v �a direita de w, isto �e, se w = a
1
: : : a
n
e v = b
1
: : : b
n
, ent~ao wv =
a
1
: : : a
n
b
1
: : : b
m
.
A reversa de uma 
adeia �e obtida es
revendo-se os s��mbolos em ordem reversa. Se w
�e a 
adeia a
ima, ent~ao a reversa de w, denotado por w
R
, �e a
n
� � �a
1
.
Se w = vu, ent~ao v diz-se um pre�xo e u um su�xo de w.
O 
omprimento de uma 
adeia w, denotado por jw j, �e o n�umero de s��mbolos que
�guram na 
adeia. A 
adeia vazia, �e aquela sem nenhum s��mbolo, que ser�a denotado
por �. Por exemplo, j� j= 0, �w = w� = w, para todo w.
Se u e v s~ao 
adeias, ent~ao
juv j=ju j + jv j : (1.2)
De fato, para mostrar esta igualdade pre
isamos de uma de�ni�
~ao mais pre
isa de
omprimento de 
adeia. Daremos a seguinte de�ni�
~ao re
ursiva.
� j� j= 0
� ja j= 1
� jwa j=jw j +1
para todo a 2 � e qualquer 
adeia w. Usaremos a indu�
~ao no 
omprimento da 
adeia
para mostrar a equa�
~ao 1.2.
Se jv j= 0, ent~ao v = �. Logo, por de�ni�
~ao,
10
Introdu�
~ao �a Teoria da Computa�
~ao:
Linguagens Formais e Computabilidade
Cap��tulo 1. Introdu�
~ao
juv j =ju j
=ju j +0
=ju j + jv j
Suponha que juv j=ju j + jv j e 
al
ulemos juva j:
juva j =juv j +1
=ju j + jv j +1
=ju j + jva j
Logo, por indu�
~ao, a igualdade �e v�alida para todo v.
Se w �e uma 
adeia, ent~ao w
n
�e a 
adeia obtida 
on
atenando w 
om ela pr�oprio n
vezes. Portanto, w
n+1
= ww
n
. No 
aso espe
ial de n = 0, w
0
= �.
Seja � �e um alfabeto. O fe
ho estrela de �, denotado por �
�
, �e o 
onjunto de todas
as 
adeias (�nitas) obtidas 
on
atenando zero ou mais s��mbolos de �. Por exemplo, se
� = fag, ent~ao
�
�
= f�; a; aa; aaa; aaaa; : : :g:
Formalmente, podemor de�nir o fe
ho estrela de um alfabeto �, indutivamente, por
1. � 2 �
�
2. Se w 2 �
�
e a 2 �, ent~ao wa 2 �
�
3. os �uni
os elementos de �
�
s~ao aqueles que podem ser obtidos apli
ando uma quan-
tidade �nita de vezes as regras 1) e 2), a
ima.
O 
onjunto �
�
sempre 
ont�em �. Para ex
luir a 
adeia vazia, de�nimos o fe
ho soma
de uma alfabeto �, por �
+
= �
�
� f�g.
Enquanto um alfabeto � �e um 
onjunto �nito, �
�
e �
+
s~ao sempre in�nitos, pois � �e
n~ao vazio e n~ao existe limite no 
omprimento das 
adeias nesses dois 
onjuntos.
Uma linguagem �e de�nida em sentido amplo 
omo um sub
onjunto de �
�
. Qualquer
adeia w, numa linguagem L, ser�a 
hamada palavra ou senten�
a de L. Na teoria
das linguagens formais n~ao distinguiremos palavras de senten�
as. Para forne
er mais
estrutura a essa de�ni�
~ao, bastante ampla, de linguagem, estudaremos m�etodos pelos
quais poderemos de�nir linguagens parti
ulares.
Exemplo 1.2.2 Seja � = fa; bg. Ent~ao �
�
= f�; a; b; aa; ab; ba; bb; aaa; aab; : : :g. O
onjunto fa; aa; aabg �e uma linguagem sobre �.
Introdu�
~ao �a Teoria da Computa�
~ao:
Linguagens Formais e Computabilidade
11
1.2. No�
~oes de Linguagens, Gram�ati
as e Auto^matos
A linguagem do exemplo anterior tem uma quantidade �nita de palavras, por isso ela
�e 
hamada linguagem �nita. O 
onjunto L = fa
n
b
n
=n � 0g �e tamb�em uma linguagem
sobre �. As 
adeias aabb e aaaabbbb s~ao palavras de L, mas a 
adeia abb n~ao est�a em L.
Esta linguagem �e in�nita.
Como as linguagens s~ao 
onjuntos, a uni~ao, a interse�
~ao e a diferen�
a de duas lin-
guagens s~ao imediatamente de�nidas. O 
omplemento de uma linguagem L, sobre o
alfabeto �, �e de�nida 
om respeito a �
�
, isto �e, o 
omplemento de L �e a liguagem, sobre
�, de�nida por
L = �
�
� L:
A 
on
atena�
~ao de duas linguagens L
1
e L
2
, sobre os alfabetos �
1
e �
2
, respe
ti-
vamente, �e a linguagem, sobre o alfabeto �
1
[ �
2
, denotada por L
1
L
2
, 
onsistindo do
onjunto de todas as 
adeias obtidas 
on
atenando-se qualquer elemento de L
1
om qual-
quer elemento de L
2
, isto �e
L
1
L
2
= fxy=x 2 L
1
e y 2 L
2
g
De�nimos L
n
omo L 
on
atenado n vezes 
om ele pr�oprio. No 
aso espe
ial de n = 0,
L
0
= f�g.
Exemplo 1.2.3 Se L = fa
n
b
n
=n � 0g, ent~ao L
2
= fa
m
b
m
a
n
b
n
=m � 0 e n � 0g. Observe
que m e n n~ao est~ao rela
ionados. A 
adeia aabbaaabbb est�a em L
2
.
O fe
ho estrela de uma linguagem L, sobre um alfabeto �, �e a linguagem L
�
, sobre
o pr�oprio �, de�nida por
L
�
=
1
[
i=0
L
i
= L
0
[ L
1
[ L
2
[ L
3
[ � � �
e o fe
ho positivo da linguagem L, denotado porL
+
, �e de�nido por
L
+
=
1
[
i=1
L
i
= L
1
[ L
2
[ L
3
[ � � �
Observe que L
+
= L
�
� L
0
= L
�
� f�g n~ao �e ne
essariamente verdade, pois se � 2 L
ent~ao, L
+
= L
�
.
12
Introdu�
~ao �a Teoria da Computa�
~ao:
Linguagens Formais e Computabilidade
Cap��tulo 1. Introdu�
~ao
1.2.2 Gram�ati
as
Para estudar linguagens, matemati
amente, pre
isamos de um me
anismo para des
reve^-
las. A linguagem do dia a dia �e impre
isa e amb��gua, portanto, a des
ri�
~ao em portugue^s,
em geral, �e inadequada. A nota�
~ao de 
onjuntos �e mais adequada, por�em limitada. Aqui,
introduziremos a no�
~ao de gram�ati
a, uma ferramenta 
omum e poderosa para de�nir
linguagens.
Uma gram�ati
a para a l��ngua portugue^sa nos diz se uma senten�
a, em parti
ular, �e
bem formada ou n~ao. Uma regra t��pi
a da gram�ati
a portugue^sa �e \uma senten�
a pode
onsistir de um substantivo, seguido por um predi
ado". Mais pre
isamente, podemos
es
rever isso 
omo
hsenten�
ai �! hfrase� substantivoihpredi
adoi
om a interpreta�
~ao �obvia. Isto �e bastante para se lidar 
om senten�
as. Devemos tamb�em
forne
er de�ni�
~oes dos 
onstrutos introduzidos na de�ni�
~ao de senten�
a
hfrase� substantivoi e hpredi
adoi. Portanto,
hfrase� substantivoi �! hartigoihsubstantivoi
hpredi
adoi �! hverboi
Se asso
iarmos a 
ada senten�
a \um" ou \uma" 
omo hartigoi, \
~ao" e \menina"
omo hsubstantivoi e \
orre" e \
aminha" 
omo hverboi, ent~ao a gram�ati
a nos diz que
as senten�
as \um 
~ao 
orre" e \uma menina 
aminha" s~ao senten�
as bem-formadas.
De�ni�
~ao 1.2.4 Uma gram�ati
a, G, �e de�nida 
omo uma qu�adrupla G = hV; T; S; P i,
onde
� V �e um 
onjunto �nito de objetos, 
hamados vari�aveis.
� T �e um 
onjunto �nito de objetos, disjunto de V , 
hamados s��mbolos terminais.
� S 2 V �e um s��mbolo espe
ial, 
hamado vari�avel de in��
io.
� P �e um 
onjunto �nito de produ�
~oes.
O prin
ipal na gram�ati
a s~ao as regras de produ�
~ao. Elas espe
i�
am 
omo a gram�ati
a
transforma uma 
adeia em outra, e atrav�es disso elas de�nem uma linguagem asso
iada
�a gram�ati
a. Assumiremos que todas as produ�
~oes s~ao da forma
x �! y;
onde x �e um elemento de (V [ T )
+
e y est�a em (V [ T )
�
. As produ�
~oes s~ao apli
adas
omo segue: dado uma 
adeia da forma
Introdu�
~ao �a Teoria da Computa�
~ao:
Linguagens Formais e Computabilidade
13
1.2. No�
~oes de Linguagens, Gram�ati
as e Auto^matos
w = uxv;
dizemos que a produ�
~ao �e apli
�avel a esta 
adeia, e podemos us�a-la para tro
ar x por y,
obtendo, assim, a nova 
adeia
z = uyv:
Neste 
aso, dizemos que w deriva z ou z �e derivada de w, denotado por w =) z.
Cadeias su
essivas s~ao derivadas apli
ando regras de produ�
~ao da gram�ati
a, numa ordem
arbitr�aria. Uma produ�
~ao pode ser usada se ela �e apli
�avel e pode ser apli
ada quantas
vezes se quizer. Se w
1
=) w
2
=) : : : =) w
n
, dizemos que w
1
deriva w
n
e es
revemos
w
1
�
=) w
n
:
A estrela � indi
a que foi 
onsiderado um n�umero n~ao espe
i�
ado de etapas (in
luindo
zero) para derivar w
n
de w
1
. Portanto, w
�
=) w sempre se d�a. Para indi
ar que, pelo
menos uma produ�
~ao foi apli
ado es
reveremos
w
+
=) v:
Apli
ando as regras de produ�
~ao em ordens diferentes, uma gram�ati
a pode gerar
muitas 
adeias. O 
onjunto de todas 
adeias �e a linguagem de�nida ou gerada pela
gram�ati
a.
De�ni�
~ao 1.2.5 Seja G = hV; T; S; P i uma gram�ati
a. O 
onjunto
L(G) = fw 2 T
�
= S
�
=) wg
�e denominado linguagem gerada pela gram�ati
a G. Os elementos de L(G) s~ao 
hamados
senten�
as ou palavras.
Se w 2 L(G), ent~ao a seque^n
ia
S =) w
1
=) w
2
=) : : : =) w
n
=) w
�e uma deriva�
~ao da senten�
a w. As 
adeias S; w
1
; w
2
; : : : ; w
n
que 
ont�em vari�aveis e
objetos terminais, s~ao 
hamados formas senten
iais da deriva�
~ao.
14
Introdu�
~ao �a Teoria da Computa�
~ao:
Linguagens Formais e Computabilidade
Cap��tulo 1. Introdu�
~ao
Exemplo 1.2.6 Considere a gram�ati
a G = hfSg; fa; bg; S; P i, onde P �e dado por
S �! aSb
S �! �:
Ent~ao, S =) aSb =) aaSbb =) aabb. Logo, podemos es
rever S
�
=) aabb.
A 
adeia aabb �e uma senten�
a na linguagem gerada por G, enquanto aaSbb �e uma
forma senten
ial.
Uma gram�ati
a G de�ne 
ompletamente a linguagem L(G), por�em pode n~ao ser f�a
il
obter uma des
ri�
~ao expl��
ita da linguagem a partir da gram�ati
a. Nesse exemplo, no
entanto, n~ao �e di�
il 
onje
turar que
L(G) = fa
n
b
n
= n � 0g
e �e f�a
il prov�a-la.
Se observarmos que a regra S �! aSb �e re
ursiva, teremos uma prova por indu�
~ao.
Mostremos que todas as formas senten
iais tem a forma w
i
= a
i
Sb
i
.
1. Se i = 0, w
0
= S
2. Suponha que w
i
= a
i
Sb
i
. Mostremos que w
i+1
= a
i+1
Sb
i+1
. Mas, de a
i
Sb
i
, apli
ando
a regra S �! aSb, obtemos a
i+1
Sb
i+1
. Observe que se apli
armos a produ�
~ao
S �! �, obteremos uma senten�
a e n~ao uma forma senten
ial. Logo, toda forma
senten
ial tem aquela forma.
Agora, apli
ando a regra S �! �, temos que todas as senten�
as tem a forma a
n
b
n
,
para n � 0.
Exemplo 1.2.7 A
har a gram�ati
a que gera L = fa
n
b
n+1
=n � 0g.
A ideia por tr�as do exemplo anterior pode ser estendido neste 
aso. Tudo que pre
i-
samos fazer �e gerar um b extra. Isto pode ser feito 
om a produ�
~ao S �! Ab, 
om outras
produ�
~oes es
olhidas tais que A possa derivar a linguagem do exemplo anterior. Com esse
ra
io
��nio, obtemos a gram�ati
a G = hfS;Ag; fa; bg; S; P i, 
om produ�
~oes P :
S �! Ab
A �! aAb
A �! �
Para se 
onven
er que essa �e a gram�ati
a pedida derive algumas senten�
as.
Introdu�
~ao �a Teoria da Computa�
~ao:
Linguagens Formais e Computabilidade
15
1.2. No�
~oes de Linguagens, Gram�ati
as e Auto^matos
Os exemplos s~ao relativamente f�a
eis, de modo que os argumentos rigorosos podem
pare
er sup�er
uos. Mas, em geral, n~ao �e f�a
il a
har a gram�ati
a para uma linguagem
des
rita informalmente ou dar uma 
ara
teriza�
~ao intuitiva da linguagem de�nida pela
gram�ati
a. Para mostrar que uma dada linguagem �e, de fato, gerada por uma gram�ati
a,
G, devemos mostrar:
� Que todo w 2 L pode ser derivado de S, usando G.
� Toda 
adeia derivada, usando G, est�a em L.
Exemplo 1.2.8 Considere a gram�ati
a G
1
= hfA; Sg; fa; bg; S; P
1
i, 
om P
1
onsistindo
das produ�
~oes:
S �! aAb j �
A �! aAb j �
Introduzimos, aqui, uma abrevia�
~ao no qual v�arias produ�
~oes 
om o mesmo lado es-
querdo s~ao es
ritos numa �uni
a linha, 
om lado direito alternativo separado por \j". Nessa
nota�
~ao, S �! aAb j � substitui as duas produ�
~oes, S �! aAb e S �! �.
Essa gram�ati
a �e equivalente, no sentido que gera a mesma linguagem, �a gram�ati
a G
do exemplo 1.2.6. A equivale^n
ia �e f�a
il de mostrar provando que L(G
1
) = fa
n
b
n
= n � 0g.
1.2.3 Auto^matos
Um auto^mato �e um modelo abstrato de um 
omputador digital. Como tal, todo auto^mato
in
lui algumas 
ara
ter��sti
as essen
iais.
^
Ele possui um me
anismo para le^r entradas.
Assumiremos que as entradas s~ao 
adeias so^bre um dado alfabeto, es
ritos numa �ta de
entrada, a qual o auto^mato pode le^r, mas n~ao alterar. A �ta de entrada �e dividida em
quadrados ou 
�elulas, 
ada um dos quais pode 
onter um s��mbolo. O me
anismo de
entradapode le^r a �ta de entrada da esquerda para a direita, um s��mbolo de 
ada vez. O
me
anismo de entrada pode dete
tar o �m da 
adeia de entrada (per
ebendo uma 
ondi�
~ao
de t�ermino da 
adeia). O auto^mato pode produzir sa��das, de alguma forma.
^
Ele pode
ter um dispositivo tempor�ario de armazenamento, 
onsistindo de um n�umero ilimitado de
�elulas, 
ada uma 
apaz de manter um �uni
o s��mbolo do alfabeto (n~ao ne
essariamente o
mesmo do alfabeto de entrada). O auto^mato pode le^r e alterar o 
onte�udo das 
�elulas de
armazenamento. Finalmente, o auto^mato possui uma unidade de 
ontrole, que pode estar
em qualquer um de um n�umero �nito de estados internos, podendo tro
ar os estados
de um modo bem de�nido. A �gura 1.3 mostra a representa�
~ao esquem�ati
a de um
auto^mato.
Assumimos que um auto^mato opera num tempo dis
reto. Em qualquer tempo da-
do, a unidade de 
ontrole est�a em algum estado interno e o me
anismo de entrada est�a
apontando para um s��mbolo parti
ular na �ta de entrada. O estado interno da unidade
16
Introdu�
~ao �a Teoria da Computa�
~ao:
Linguagens Formais e Computabilidade
Cap��tulo 1. Introdu�
~ao
Estado
Interno
Fita de Entrada
Unidade de
Controle
Saida
A
rea de A
rm
azenam
ento
Figura 1.3: Representa�
~ao esquem�ati
a de um auto^mato.
de 
ontrole na pr�oxima etapa de tempo �e determinado pelo pr�oximo-estado ou fun�
~ao de
transi�
~ao. Esta fun�
~ao de transi�
~ao forne
e o pr�oximo estado, em fun�
~ao do estado 
or-
rente, o s��mbolo de entrada 
orrente e a informa�
~ao 
orrente na �area de armazenamento
tempor�aria. Durante a transi�
~ao de um intervalo de tempo ao pr�oximo, a sa��da pode
ser produzida, ou tro
ada informa�
~ao na �area de armazenamento tempor�ario. O termo
on�gura�
~ao ser�a usado para referir a um estado parti
ular da unidade de 
ontrole, a �ta
de entrada e o armazenamento tempor�ario. A transi�
~ao do auto^mato de uma 
on�gura�
~ao
para a pr�oxima ser�a um movimento.
Esse modelo geral 
obre todos os auto^matos que dis
utiremos neste 
urso.
Introdu�
~ao �a Teoria da Computa�
~ao:
Linguagens Formais e Computabilidade
17
1.2. No�
~oes de Linguagens, Gram�ati
as e Auto^matos
18
Introdu�
~ao �a Teoria da Computa�
~ao:
Linguagens Formais e Computabilidade
Cap��tulo 2
Auto^matos Finitos
Neste 
ap��tulo, veremos a 
lasse mais simples de auto^matos, denominados auto^matos
�nitos, os quais podem ser 
lassi�
ados em determin��sti
os e n~ao determin��sti
os.
2.1 Auto^matos Finitos Determin��sti
os
Um auto^mato re
onhe
edor �e aquele que para 
ada 
adeia na �ta de entrada diz se ela �e
a
eita ou n~ao. Ou seja, diz se uma 
adeia de s��mbolos faz parte ou n~ao de uma linguagem.
Um re
onhe
edor �nito �e um auto^mato re
onhe
edor que n~ao usa �area de armazenamento
e que sempre p�ara (para isto, le^ uma 
�elula uma �uni
a vez).
De�ni�
~ao 2.1.1 Um Auto^mato �nito determin��sti
o (afd) �e uma qu��ntupla
M = hQ;�; Æ; q
0
; F i, onde
� Q �e um 
onjunto �nito de estados internos,
� � �e um 
onjunto �nito de s��mbolos, 
hamado alfabeto de entrada,
� Æ : Q� � �! Q �e uma fun�
~ao total, 
hamada fun�
~ao de transi�
~ao,
� q
0
2 Q �e o estado ini
ial,
� F � Q �e o 
onjunto de estados �nais ou estados de a
eita�
~ao .
Um afd opera 
omo segue: No in��
io assumimos que e^le est�a no estado ini
ial q
0
,
om seu me
anismo de entrada apontando para o s��mbolo mais �a esquerda da 
adeia de
entrada. Durante 
ada movimento do auto^mato, o me
anismo de entrada avan�
a uma
posi�
~ao para a direita, 
onsumindo um s��mbolo de entrada. Quando for atingido o �m da
adeia, esta ser�a a
eita se o auto^mato estiver num de seus estados �nais. Caso 
ontr�ario,
a 
adeia �e rejeitada. O me
anismo de entrada pode se mover, somente, da esquerda para
19
2.1. Auto^matos Finitos Determin��sti
os
a direita, lendo exatamente, um s��mbolo em 
ada etapa. Observe que quando a exe
u�
~ao
de um auto^mato atinge um estado �nal, isso n~ao signi�
a que a exe
u�
~ao �nalizou, pois
ela s�o termina quando o auto^mato le^ toda a entrada na �ta.
Para visualizar e representar um auto^mato �nito usamos grafos de transi�
~ao, nos quais
os v�erti
es representam os estados e as arestas representam as transi�
~oes. Os r�otulos
dos v�erti
es s~ao os nomes dos estados, enquanto os r�otulos das arestas s~ao os valores
orrentes dos s��mbolos de entrada. Por exemplo, se q
0
e q
1
s~ao estados de algum afd
M , o grafo asso
iado a M ter�a um v�erti
e rotulado 
om q
0
e outro rotulado 
om q
1
.
Uma aresta (q
0
; q
1
), rotulada por a, representa a transi�
~ao Æ(q
0
; a) = q
1
. O estado ini
ial
ser�a identi�
ado por uma seta n~ao-rotulada 
hegando ao v�erti
e. Os estados �nais ser~ao
identi�
ados por um 
��r
ulo duplo.
Mais formalmente, se M = hQ;�; Æ; q
0
; F i �e um afd, ent~ao a e^le est�a asso
iado um
grafo de transi�
~ao, G
M
, tendo exatamente jQ j v�erti
es, 
ada um rotulado 
om um q
i
2 Q
diferente. Para 
ada regra de transi�
~ao Æ(q
i
; a) = q
j
, o grafo tem uma aresta (q
i
; q
j
),
rotulada a. O v�erti
e asso
iado a q
0
�e 
hamado v�erti
e ini
ial, enquanto que aqueles
rotulados a q
f
2 F s~ao os v�erti
es �nais.
�
E muito simples 
onverter a de�ni�
~ao de um
afd, M = hQ;�; Æ; q
0
; F i, no seu grafo de transi�
~ao e vi
e-versa.
Exemplo 2.1.2 O grafo da �gura 2.1 representa o afdM = hfq
0
; q
1
; q
2
g; f0; 1g; Æ; q
0
; fq
1
gi,
onde Æ �e dado por
Æ(q
0
; 0) = q
0
; Æ(q
0
; 1) = q
1
Æ(q
1
; 0) = q
0
; Æ(q
1
; 1) = q
2
Æ(q
2
; 0) = q
2
; Æ(q
2
; 1) = q
1
:
Este afd a
eita a 
adeia 01. Ini
ia no estado q
0
e aponta para o s��mbolo 0. Este �ultimo
fato �e representado pela aresta do grafo rotulada 
om 0. Observamos que o auto^mato
permane
e no estado q
0
. Ap�os o s��mbolo 1 ter sido lido o auto^mato entra no estado q
1
.
Estamos agora no �m da 
adeia e, ao mesmo tempo, no estado �nal q
1
. Portanto, a
adeia 01 �e a
eita. O afd n~ao a
eita a 
adeia 00, porque ap�os le^r dois 0's 
onse
utivos
ele n~ao estar�a no estado q
1
, mas em q
0
. Ra
io
inando de modo an�alogo, vemos que o
auto^mato a
eitar�a as 
adeias 101, 00111 e 11001, mas n~ao a
eitar�a 100 nem 1100.
�
E 
onveniente introduzir a fun�
~ao de transi�
~ao estendida Æ
�
: Q � �
�
�! Q.
O segundo argumento de �
�
�e uma 
adeia, em vez de um �uni
o s��mbolo, e seu valor �e o
estado do auto^mato, ap�os le^ aquela 
adeia. Por exemplo, no 
aso do afd do exemplo 2.1.2,
Æ
�
(q
0
; 001) = q
1
e Æ
�
(q
1
; 1110) = q
2
. Formalmente, podemos de�nir Æ
�
, re
ursivamente,
por
1. Æ
�
(q; �) = q
2. Æ
�
(q; wa) = Æ(Æ
�
(q; w); a)
20
Introdu�
~ao �a Teoria da Computa�
~ao:
Linguagens Formais e Computabilidade
Cap��tulo 2. Auto^matos Finitos
q q q0 1 2
0
0
1 1
0
1
Figura 2.1: Exemplo de afd.
Para todo q 2 Q, w 2 �
�
e a 2 �. Para ve^r 
omo essa nota�
~ao �e adequada, vamos
apli
ar essas de�ni�
~oes ao exemplo anterior.
Æ
�
(q
0
; 01) = Æ(Æ
�
(q
0
; 0); 1) apli
ando 2)
= Æ(Æ(Æ
�
(q
0
; �); 0); 1) apli
ando 2) e 0 = �0
= Æ(Æ(q
0
; 0); 1) apli
ando 1)
= Æ(q
0
; 1) apli
ando Æ
= q
1
apli
ando Æ
2.2 Linguagens e afd's
Tendo de�nido pre
isamente um afd podemos, agora, de�nir formalmente o que enten-
demos por uma linguagemasso
iada a um afd. A asso
ia�
~ao �e obvia: a linguagem �e o
onjunto de todas as 
adeias re
onhe
idas pelo auto^mato.
De�ni�
~ao 2.2.1 A linguagem a
eita por um afd, M = hQ;�; Æ; q
0
; F i, denotado por
L(M), �e o 
onjunto de todas as 
adeias, so^bre �, a
eitas por M . Formalmente,
L(M) = fw 2 �
�
= Æ
�
(q
0
; w) 2 Fg
Observe a exige^n
ia de que Æ, e 
onsequentemente Æ
�
, seja uma fun�
~ao total. Em 
ada
etapa, um movimento �uni
o �e de�nido, isto justi�
a o nome determin��sti
o, para esse
auto^mato.
Um afd pro
essar�a toda 
adeia em �
�
, a
eitando-a ou n~ao. N~ao a
eita�
~ao signi�
a
que o afd p�ara, num estado n~ao �nal tal que
L(M) = fw 2 �
�
= Æ(q
0
; w) 62 Fg:
Exemplo 2.2.2 Considere o afd, na �gura 2.2.
Introdu�
~ao �a Teoria da Computa�
~ao:
Linguagens Formais e Computabilidade
21
2.2. Linguagens e afd's
q q q0 1 2
a
b a,b
a,b
Figura 2.2: Exemplo de afd.
Ao desenhar a �gura 2.2, permitimos o uso de dois r�otulos numa mesma aresta.
Tal multipli
idade de arestas �e uma abrevia�
~ao para duas ou mais transi�
~oes distintas: a
transi�
~ao �e tomada se o s��mbolo de entrada 
ombina 
om qualquer dos r�otulos da aresta.
O auto^mato da �gura 2.2 permane
e no seu estado ini
ial, q
0
, at�e o primeiro b ser
lido. Se este �e tamb�em o �ultimo s��mbolo da entrada, ent~ao a 
adeia �e a
eita. Se n~ao, o afd
vai para o estado q
2
, do qual nun
a es
apa. Tal estado �e 
hamado um estado de morte.
Como podemos ver no grafo, o auto^mato a
eita todas as 
adeias que tem exatamente um
b, lo
alizado na posi�
~ao mais �a direita da 
adeia. Todas as outras 
adeias s~ao rejeitadas.
Em nota�
~ao de 
onjunto, a linguagem a
eita por este auto^mato �e
L = fa
n
b= n � 0g
Teorema 2.2.3 Seja M = hQ;�; Æ; q
0
; F i um afd, e seja G
M
seu grafo asso
iado. Ent~ao
para todo q
i
; q
j
2 Q e w 2 �
+
, Æ
�
(q
i
; w) = q
j
se e somente se existe em G
M
um 
aminho
om r�otulo w de q
i
a q
j
.
Demonstra
�
~
ao: Este fato �e �obvio, examinando os exemplos 2.1.2 e 2.2.2. Podemos
provar isso, rigorosamente, usando a indu�
~ao no 
omprimento de w. Suponha que o
teorema �e verdadeiro para todas as 
adeias v, 
om 
omprimento jv j� n. Considere uma
adeia w de 
omprimento jw j= n+1 e es
reva 
omo w = va, para algum a 2 �. Suponha,
agora, que Æ
�
(q
i
; v) = q
k
. Como j v j= n, deve existir um 
aminho em G
M
, rotulado por
v, de q
i
a q
k
. Mas se Æ
�
(q
i
; w) = q
j
, ent~ao M deve ter uma transi�
~ao Æ(q
k
; a) = q
j
, tal que
por 
onstru�
~ao G
M
tem uma aresta (q
k
; q
j
), 
om r�otulo a. Portanto, existe um 
aminho
em G
M
, rotulado va = w, de q
i
a q
j
. Como o resultado �e obviamente verdadeiro para
n = 1, podemos argumentar, por indu�
~ao, que para todo w 2 �
+
,
Æ
�
(q
i
; w) = q
j
o que impli
a que existe um 
aminho em G
M
de q
i
a q
j
, rotulado w. Um argumento
simples mostra que a existe^n
ia de tal 
aminho impli
a 2.2, 
ompletando a prova.
Uma outra maneira de representar um auto^mato �e atrav�es de uma matriz (tabela). A
tabela da �gura 2.3 �e equivalente �a da �gura 2.2. Aqui, os r�otulos da linha representam
os estados 
orrentes e os das 
olunas representam o s��mbolo de entrada 
orrente.
22
Introdu�
~ao �a Teoria da Computa�
~ao:
Linguagens Formais e Computabilidade
Cap��tulo 2. Auto^matos Finitos
a b
q
0
q
0
q
1
q
1
q
2
q
2
q
2
q
2
q
2
Figura 2.3: representa�
~ao por tabela da afd do exemplo.
Exemplo 2.2.4 A
har um afd que re
onhe�
a todas as 
adeias, so^bre o alfabeto
� = fa; bg, 
om pre�xo ab.
A �uni
a exige^n
ia, aqui, �e que os dois primeiros s��mbolos na 
adeia sejam a e b,
respe
tivamente. Ap�os eles terem sido lidos n~ao resta nenhuma de
is~ao mais a ser tomada.
Podemos, portanto, resolver o problema 
om um auto^mato que tem quatro estados: um
estado ini
ial, dois estados para re
onhe
er ab, um estado de morte �nal e outro n~ao �nal.
Se o primeiro s��mbolo �e a e o segundo b, o auto^mato vai para o estado �nal de morte, onde
ele �
ar�a, pois as entradas restantes n~ao traz problemas. Por outro lado, se o primeiro
s��mbolo n~ao �e a ou o segundo n~ao �e b, o auto^mato entra num estado n~ao �nal de morte.
A solu�
~ao �e mostrada na �gura 2.4.
q q q
q
0 1 2
3
a b
a
b
a,b
a,b
Figura 2.4: Exemplo de afd.
Exemplo 2.2.5 A
har um afd que a
eita todas as 
adeias, so^bre f0; 1g, ex
eto aquelas
ontendo a sub
adeia 001.
Para de
idir se a sub
adeia 001 o
orreu, pre
isamos 
onhe
er n~ao somente o s��mbolo de
entrada 
orrente, mas tamb�em relembrar se ele foi pre
edido por dois 0's ou n~ao. Podemos
ontrolar isso 
olo
ando o auto^mato num estado espe
���
o e rotulando-o adequadamente.
Assim, 
omo os nomes de vari�aveis em linguagens de programa�
~ao s~ao mnemo^ni
os, isto
�e, nomes que denotam o papel da vari�avel no programa, os nomes de estados s~ao arbi-
tr�arios e, portanto, tamb�em, podem ser es
olhidos por raz~oes mnemo^ni
as. Por exemplo,
Introdu�
~ao �a Teoria da Computa�
~ao:
Linguagens Formais e Computabilidade
23
2.2. Linguagens e afd's
o estado no qual dois 0's imediatamente pre
edem um s��mbolo pode ser rotulado, simples-
mente, por 00.
Se a 
adeia 
ome�
a 
om 001, ent~ao ela �e rejeitada. Isso impli
a que deve existir um
aminho, rotulado 001, do estado ini
ial ao estado n~ao �nal. Por 
onvenie^n
ia, esse
estado n~ao �nal �e rotulado 001. Esse estado deve ser de morte, pois o s��mbolo que vem
ap�os n~ao traz problemas. Todos os outros estados s~ao estados �nais ou a
eitadores.
Isso nos d�a a estrutura b�asi
a da solu�
~ao, mas devemos, ainda, a
res
entar 
ondi�
~oes
para o 
aso da sub
adeia 001 o
orrer no meio da 
adeia de entrada. Devemos de�nir Q
e Æ de tal modo que sempre que pre
isarmos de uma de
is~ao 
orreta ela seja relembrada
pelo auto^mato. Nesse 
aso, quando um s��mbolo for lido, pre
isamos 
onhe
er alguma
parte da 
adeia para a esquerda, por exemplo, se ou n~ao os dois s��mbolos anteriores foram
00. Se rotularmos os estados 
om s��mbolos relevantes, �e f�a
il ve^r quais transi�
~oes devem
ser. Por exemplo, Æ(00; 0) = 00, pois esta situa�
~ao apare
e somente se existem tre^s 0's
onse
utivos. Estamos, somente, interessados nos dois �ultimos, o que o deixa no mesmo
estado 00. A solu�
~ao 
ompleta �e mostrada na �gura 2.5, abaixo.
0 00 001\
1
0
0 1
0
1
0,1
Figura 2.5: Exemplo de afd.
Exemplo 2.2.6 Desenhar um afd que re
onhe�
a a linguagem, L, de todas as 
adeias,
sobre o alfabeto � = fa; bg, 
om uma quantidade par de a's e de b's. Isto �e,
L = fw 2 � j N
a
(w) e N
b
(w) s~ao paresg;
onde, N
a
(w) �e uma fun�
~ao que devolve o n�umero de s��mbolos, a's, que o
orrem em w.
Um auto^mato que re
onhe�
a esta linguagem deve permitir que em qualquer momento
da 
omputa�
~ao possamos saber a quantidade de a's e de b's que foi lido. Mas, na verdade,
s�o �e ne
ess�ario \memorizar" se at�e esse momento a quantidade de a's e de b's, s~ao, ambos
pares, ambos ��mpares, os a's s~ao pares e os b's ��mpares ou se os a's s~ao ��mpares e os b's
pares. Se 
onsiderarmos 0 
omo par, ent~ao quando 
ome�
a a 
omputa�
~ao do auto^mato,
ele se en
ontra no estado no qual ambos s~ao pares, se logo emseguida le^ um a, ent~ao altera
para o estado no qual a quantidade de a's s~ao ��mpares e as de b's pares, et
. Assim, o
auto^mato deve 
onsiderarsomente quatro estados, simbolizando 
ada uma dessas poss��veis
ombina�
~oes. O estado par-par, �e ambos, ini
ial e �nal. A �gura 2.6 ilustra do gr�afo do
auto^mato des
rito aqui.
24
Introdu�
~ao �a Teoria da Computa�
~ao:
Linguagens Formais e Computabilidade
Cap��tulo 2. Auto^matos Finitos
PP
PI
IP
II
a
b
a
b
a
b
a
b
Figura 2.6: Exemplo de afd.
Neste auto^mato os nomes dos estados n~ao s~ao os tradi
ionais q
i
, mas PP, PI, IP e
II. Estes nomes s~ao mais mnemo^ni
os, isto �e, deixam em evide^n
ia o estado da m�aquina
em termos da situa�
~ao par
ial da paridade de a's e de b's. Assim, o estado PP, simboliza
a situa�
~ao de uma quantidade par de a's e de b's, o estado PI indi
a uma quantidade par
de a's e ��mpar de b's, et
.
2.3 Linguagens Regulares
De�ni�
~ao 2.3.1 Uma linguagem, L, diz-se regular se e somente se existe algum afd M
tal que
L = L(M):
Exemplo 2.3.2 Mostre que a linguagem L = fawa = w 2 fa; bg
�
g �e regular.
Devemos a
har uma afd que re
onhe�
a a linguagem L. Assim, o afd deve 
he
ar
se uma 
adeia, 
ome�
ando 
om a, tamb�em termina 
om a. O que est�a no meio n~ao �e
importante. A solu�
~ao �e 
ompli
ada pelo fato de n~ao existir um modo expl��
ito de testar
o �nal da 
adeia. Essa di�
uldade pode ser superada pondo o afd num estado �nal se o
segundo a fo^r en
ontrado. Se este n~ao for o �ultimo, e se depois dele vier um b ent~ao e^le
tirar�a o auto^mato do estado �nal. A pesquisa 
ontinuar�a dessa maneira, 
ada a fazendo,
o auto^mato ir (ou 
ontinuar, se fo^r o 
aso) para o estado �nal. A solu�
~ao 
ompleta est�a
mostrada na �gura 2.7. Novamente, fa�
a alguns exemplos para testar seu resultado.
Exemplo 2.3.3 Seja L a linguagem do exemplo anterior. Mostrar que L
2
�e regular.
Novamente, mostraremos que a linguagem �e regular 
onstruindo um afd para ela. Po-
demos es
rever, expli
itamente, uma express~ao para L
2
, qual seja
L
2
= faw
1
aaw
2
a = w
1
; w
2
2 fa; bg
�
g
Introdu�
~ao �a Teoria da Computa�
~ao:
Linguagens Formais e Computabilidade
25
2.3. Linguagens Regulares
q q q
q
0
1
2 3
a
b
b
a
ab
a,b
Figura 2.7: Exemplo de afd.
Portanto, pre
isamos de um afd para re
onhe
er duas 
adeias 
onse
utivas de formas
essen
ialmente iguais (mas n~ao ne
essariamente ide^nti
as em valores). O diagrama na
�gura 2.7 pode ser usado 
omo ponto de in��
io, mas o v�erti
e q
3
tem de ser modi�
ado.
Este estado n~ao pode mais ser �nal pois, neste ponto, devemos 
ome�
ar a olhar para a
segunda sub
adeia da forma awa. Para re
onhe
er a segunda sub
adeia, tomamos uma
r�epli
a dos estados na primeira parte (
om novos nomes), 
om q
3
no in��
io da segunda
parte. Como a 
adeia 
ompleta pode ser quebrada em suas partes 
onstituintes se aa
o
orrer, deixamos a o
orre^n
ia de aa disparar o auto^mato para a segunda parte. Podemos
obter isso fazendo Æ(q
3
; a) = q
4
. A solu�
~ao 
ompleta est�a na �gura 2.8
q q q
q
0
1
2 3
a
b
b
a
ab
a,b
a
a
b
a
q q4 5
Figura 2.8: Exemplo de afd.
26
Introdu�
~ao �a Teoria da Computa�
~ao:
Linguagens Formais e Computabilidade
Cap��tulo 2. Auto^matos Finitos
Este exemplo sugere a 
onje
tura de que se L �e regular, ent~ao L
2
; L
3
; : : : tamb�em s~ao.
2.4 Auto^matos Finitos N~ao Determin��sti
os
N~ao determinismo signi�
a uma es
olha de movimentos para um auto^mato. Em vez de
pres
rever um �uni
o movimento em 
ada situa�
~ao, permitimos um 
onjunto de movimen-
tos poss��veis. Formalmente, 
onseguiremos isso de�nindo a fun�
~ao de transi�
~ao tal que
sua imagem seja um 
onjunto de estados poss��veis.
De�ni�
~ao 2.4.1 Um auto^mato �nito n~ao determin��sti
o (afn) �e de�nido 
omo a
qu��ntupla
M = hQ;�; Æ; q
0
; F i
onde Q;�; q
o
e F s~ao de�nidos 
omo para afd, mas
Æ : Q� (� [ f�g) �! 2
Q
:
Observe que existem duas diferen�
as prin
ipais entre essa de�ni�
~ao e a de afd. Num
auto^mato n~ao determin��sti
o, a imagem de Æ �e o 
onjunto das partes de Q, 2
Q
. Logo, seu
valor n~ao �e um �uni
o elemento de Q, mas um sub
onjunto dele. Este sub
onjunto de�ne
o 
onjunto de todos os estados poss��veis que podem ser al
an�
ados pela transi�
~ao. Se,
por exemplo, o estado 
orrente �e q
1
, est�a sendo lido o s��mbolo a e
Æ(q
1
; a) = fq
0
; q
2
g;
ent~ao q
0
ou q
2
pode ser o pr�oximo estado do afn. Permitimos, tamb�em, � ser o segundo ar-
gumento de Æ. Isto signi�
a que o afn pode fazer uma transi�
~ao sem 
onsumir um s��mbolo
de entrada. Este tipo de transi�
~ao �e 
hamada �-transi�
~ao . Assim, Embora assumi-
mos que o me
anismo de entrada pode somente se deslo
ar da esquerda para a direita, �e
poss��vel, apli
ando �-transi�
~oes, que ele �que esta
ionado sobre alguns movimentos.
Analogamente aos afd's, os auto^matos n~ao determin��sti
os podem ser representados
por grafos de transi�
~ao.
Os v�erti
es s~ao determinados por Q, enquanto uma aresta (q
i
; q
j
), 
om r�otulo a, est�a
no grafo se, e somente se, q
j
2 Æ(q
i
; a). Observe que 
omo a pode ser uma 
adeia vazia,
pode existir alguma aresta 
om r�otulo �.
Uma 
adeia �e a
eita por um afn se existir uma poss��vel seque^n
ia de movimentos que
levar�a a m�aquina a um estado �nal no �m da 
adeia.
Introdu�
~ao �a Teoria da Computa�
~ao:
Linguagens Formais e Computabilidade
27
2.4. Auto^matos Finitos N~ao Determin��sti
os
q
q q q
q q
0
1 2 3
4 5
a
a
a
a
a b
Figura 2.9: Exemplo de afn.
Exemplo 2.4.2 Considere o grafo de transi�
~ao na �gura 2.9. Ele des
reve um afn 
om
duas transi�
~oes rotuladas a saindo de q
0
. Este afn re
onhe
e as 
adeias de tamanho par
de a's e a 
adeia aab.
Observe que para qualquer 
adeia 
ome�
ando 
om o s��mbolo b, o auto^mato n~ao o
re
onhe
eria, pois no estado ini
ial q
0
ele s�o admite transi�
~oes rotuladas por a.
Exemplo 2.4.3 No afn da �gura 2.10 algumas transi�
~oes, tais 
omo Æ(q
1
; 0), n~ao s~ao
espe
i�
adas no grafo e podem ser interpretadas 
omo uma transi�
~ao ao 
onjunto vazio,
isto �e, Æ(q
1
; 0) = ;. O auto^mato re
onhe
e as 
adeias 0001010 e 0101010, mas n~ao 110,
nem 010100. Observe que para 00 existem dois 
aminhos alternativos, um levando a q
o
, o
outro a q
1
. Embora q
0
n~ao seja um estado �nal, a 
adeia �e re
onhe
ida, porque �e su�
iente
que um 
aminho leve a um estado �nal.
q q q0 1 2
0
0
1
0
Figura 2.10: Exemplo de afn.
Exemplo 2.4.4 A �gura 2.11 representa um afn 
om �-transi�
~oes. Este afn re
onhe
e
adeias do tipo 0
n
1
m
2
p
om n;m; p � 0. Observe que ele a
eita a 
adeia 11222, a qual
�e equivalente �a 
adeia �11�222. Assim, antes de 
onsumir o primeiro 1, o auto^mato
faz uma �-transi�
~ao e \pula" para o estado q
1
, nele 
onsome o primeiro e o segundo 1,
depois novamente realiza uma �-transi�
~ao indo, imediatamente, para o estado q
2
no qual
onsome os tre^s 2 restantes. Como q
2
�e um estado �nal ele a
eita esta 
adeia.
Como j�a tivemos oportunidade de observar para afd's, a fun�
~ao de transi�
~ao pode
ser estendida de modo que seu segundo argumento seja uma 
adeia. Por�em, 
omo dado
28
Introdu�
~ao �a Teoria da Computa�
~ao:
Linguagens Formais e Computabilidade
Cap��tulo 2. Auto^matos Finitos
q q q0 1 2
0 1 2
Figura 2.11: Exemplo de um afn 
om �-transi�
~oes.
um estado e um s��mbolo ele pode ir a mais (ou nenhum) estados, Æ
�
(q; w)