Fundamentos em Teoria da ComputaЗ╞o
303 pág.

Fundamentos em Teoria da ComputaЗ╞o


DisciplinaFundamentos de Teoria da Computação140 materiais530 seguidores
Pré-visualização50 páginas
t´\u131picas de uma linguagem de programac¸a\u2dco de alto n´\u131vel.
Cada transic¸a\u2dco sob d e´, na realidade, uma abreviac¸a\u2dco para 10 transic¸o\u2dces: uma para cada
um dos d´\u131gitos de 0 a 9. Matematicamente, o AFD e´ uma qu´\u131ntupla (E,\u3a3, \u3b4, e0, F ), onde:
66
Entrada: (1) o AFD, dado por i, F e D, e
(2) a palavra de entrada, dada por prox .
Sa´\u131da: sim ou na\u2dco.
e\u2190 i; s\u2190 prox();
enquanto s 6= fs fac¸a
e\u2190 D[e, s]; s\u2190 prox();
fimenquanto;
se e \u2208 F enta\u2dco
retorne sim
sena\u2dco
retorne na\u2dco
fimse
Figura 2.5: Algoritmo para simular AFD\u2019s.
\u2022 E = {e0, e1, e2, e3, e4, e5, e6, e7, ee} (ee e´ o \u201cestado de erro\u201d)
\u2022 \u3a3 = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, .,+,\u2212, E}
\u2022 F = {e3, e7}
\u2022 \u3b4 e´ dada por (novamente, d representa cada um dos d´\u131gitos de 0 a 9):
\u3b4 d . + - E
e0 e2 e4 e1 e1 ee
e1 e2 e4 ee ee ee
e2 e2 e3 ee ee e5
e3 e3 ee ee ee e5
e4 e3 ee ee ee ee
e5 e7 ee e6 e6 ee
e6 e7 ee ee ee ee
e7 e7 ee ee ee ee
ee ee ee ee ee ee
Antes de apresentar algumas propriedades dos AFD\u2019s e seu relacionamento com ou-
tros formalismos importantes, sera\u2dco apresentados mais alguns exemplos. Daqui para
frente, sera´ dada e\u2c6nfase a auto\u2c6matos finitos como reconhecedores. Tenha em mente, en-
tretanto, que o conceito pode ser usado em va´rios contextos, na\u2dco necessariamente como
reconhecedores, como mostra o primeiro exemplo da sec¸a\u2dco anterior.
Exemplo 56 Sera´ apresentado um AFD M tal que:
L(M) = {w \u2208 {0, 1}\u2217 | w tem um nu´mero par de s´\u131mbolos}.
Apo´s lido um prefixo x de uma palavra, o que se deve saber para prosseguir no reconhe-
cimento da mesma? Ora, na\u2dco e´ dif´\u131cil perceber que se deve saber apenas se x tem um
nu´mero par ou \u131´mpar de s´\u131mbolos. Assim, o auto\u2c6mato tera´ apenas dois estados: par e
67
-
\ufffd\ufffd\ufffd\ufffde0 -+,-
@
@
@
@@R
.
\ufffd
\ufffd
\ufffd
\ufffd
d
A
A
A
AU\ufffd\ufffd\ufffd\ufffde1 -d
?
.\ufffd\ufffd\ufffd\ufffde4 d
6
\ufffd\ufffd\ufffd\ufffde2
\ufffd\ufffd
?
d
-.
\ufffd\ufffd\ufffd\ufffd\ufffd\ufffd\ufffd
e3
\ufffd\ufffd
?
d
-E
\ufffd\ufffd\ufffd\ufffde5 -+,- \ufffd\ufffd\ufffd\ufffde6
A
A
A
AU
d
\ufffd
\ufffd
\ufffd
\ufffd\ufffd
d\ufffd\ufffd\ufffd\ufffd\ufffd\ufffd\ufffd
e7\ufffd\ufffd6
d
\ufffd
\ufffd
\ufffd
\ufffd
E
A
A
A
AU
Figura 2.6: Reconhecendo constantes reais.
-
\ufffd\ufffd \ufffd\ufffd\ufffd\ufffd \ufffd
par -
0, 1
\ufb00
0, 1
\ufffd\ufffd \ufffd\ufffd\u131´mpar
Figura 2.7: Reconhecendo nu´mero par de s´\u131mbolos.
\u131´mpar . O diagrama de estados esta´ mostrado na Figura 2.7. Em linguagem matema´tica,
o auto\u2c6mato seria uma qu´\u131ntupla
M = ({par, \u131´mpar}, {0, 1}, \u3b4, par, {par})
onde \u3b4 e´ dada por:
\u3b4 0 1
par \u131´mpar \u131´mpar
\u131´mpar par par
Exemplo 57 Agora apresenta-se um AFD N tal que L(N) = {w \u2208 {0, 1}\u2217 | w tem um
nu´mero par de 0\u2019s e um nu´mero par de 1\u2019s}.
Neste caso, apo´s um prefixo deve-se saber se o nu´mero de 0\u2019s e´ par ou \u131´mpar e se
o nu´mero de 1\u2019s e´ par ou \u131´mpar, para que se tenha controle da paridade de ambos os
d´\u131gitos todo tempo. O diagrama de estados esta´ mostrado na Figura 2.8. O estado pp
representa a situac¸a\u2dco em que o nu´mero de 0\u2019s e de 1\u2019s e´ par, pi representa a situac¸a\u2dco
em que o nu´mero de 0\u2019s e´ par e o de 1\u2019s e´ \u131´mpar, e assim por diante. Em linguagem
matema´tica, o auto\u2c6mato seria uma qu´\u131ntupla
N = ({pp, pi, ip, ii}, {0, 1}, \u3b4, pp, {pp})
onde \u3b4 e´ dada por:
\u3b4 0 1
pp ip pi
pi ii pp
ip pp ii
ii pi ip
68
-
\ufffd\ufffd\ufffd\ufffd\ufffd\ufffd\ufffd
pp -0\ufb00
0
\ufffd\ufffd\ufffd\ufffdip
?
1
6
1
\ufffd\ufffd\ufffd\ufffdpi -0\ufb00
0
\ufffd\ufffd\ufffd\ufffdii?
1
6
1
Figura 2.8: Reconhecendo nu´meros pares de 0\u2019s e de 1\u2019s.
Se o auto\u2c6mato N do Exemplo 57 tivesse como estados finais os estados pp e ii, ele
aceitaria a mesma linguagem que o AFD do Exemplo 56. E´ fa´cil perceber que se uma
linguagem pode ser reconhecida por AFD\u2019s, enta\u2dco ela pode ser reconhecida por inu´meros
AFD\u2019s.
Definic¸a\u2dco 4 Dois AFD\u2019s, M1 e M2, sa\u2dco ditos equivalentes se, e somente se, L(M1) =
L(M2).
Dado que podem existir va´rios AFD\u2019s equivalentes para uma linguagem, tem sentido
indagar se existiria um AFD \u201cm\u131´nimo\u201d para uma linguagem. Se for assumido um alfabeto
m\u131´nimo (sem s´\u131mbolos inu´teis), existem duas entidades que influenciam o tamanho de
um AFD: os nu´meros de estados e de transic¸o\u2dces. Como a func¸a\u2dco de transic¸a\u2dco e´ total,
o nu´mero de transic¸o\u2dces e´ func¸a\u2dco apenas do nu´mero de estados: quanto menos estados,
menos transic¸o\u2dces. Ou seja, tem sentido dizer que um AFD para reconhecer uma linguagem
e´ m\u131´nimo se nenhum outro que reconhec¸a a mesma linguagem tem um nu´mero de estados
menor. Na pro´xima sec¸a\u2dco vai ser apresentado um algoritmo que, dado um AFD qualquer,
determina um AFD m\u131´nimo equivalente. Antes disso, pore´m, sera´ apresentado mais um
exemplo.
Exemplo 58 Na Figura 2.9 apresenta-se os diagramas de estado de dois AFD\u2019s, um que
reconhece A0 = {0y | y \u2208 {0, 1}\u2217}, e outro que reconhece A1 = {x1 | x \u2208 {0, 1}\u2217}. O
estado inicial de ambos e´ denominado \u3bb, o estado ci e´ atingido para palavras que comec¸am
com i, e o estado ti e´ atingido para palavras que terminam com i, para i = 0 ou 1.
Suponha que se queira um AFD que reconhec¸a a linguagem de todas as palavras de
{0, 1}\u2217 que comec¸am com 0 ou terminam com 1 e que tenham um nu´mero par de 0\u2019s e
um nu´mero par de 1\u2019s, ou seja, a linguagem L = (A0 \u222a A1) \u2229 L(N), onde A0 e A1 sa\u2dco
as linguagens do Exemplo 58 e N e´ o AFD do Exemplo 57. Seria poss´\u131vel obter um
AFD para L a partir de N e dos AFD\u2019s cujos diagramas de estado esta\u2dco apresentados na
Figura 2.9? A resposta e´ sim; algoritmos para isto sera\u2dco esboc¸ados na Sec¸a\u2dco 2.2.3.
69
-
\ufffd\ufffd\ufffd\ufffd\u3bb\ufffd
\ufffd\ufffd
\ufffd\ufffd
\ufffd*
0
\ufffd\ufffd\ufffd\ufffd\ufffd\ufffd\ufffd
c0 \ufffd\ufffd\ufb00 0,1
HHHHHHj1 \ufffd\ufffd\ufffd\ufffdc1 \ufffd\ufffd\ufb00 0,1
(a) Reconhecendo {0}{0, 1}\u2217.
-
\ufffd\ufffd\ufffd\ufffd\u3bb\ufffd
\ufffd\ufffd
\ufffd\ufffd
\ufffd*
0
\ufffd\ufffd\ufffd\ufffdt0 \ufffd\ufffd\ufb00 0
HHHHHHj1 \ufffd\ufffd\ufffd\ufffd\ufffd\ufffd\ufffd
t1 \ufffd\ufffd\ufb00 1?
1
6
0
(b) Reconhecendo {0, 1}\u2217{1}.
Figura 2.9: Reconhecendo {0}{0, 1}\u2217 e {0, 1}\u2217{1}.
2.2.2 Minimizac¸a\u2dco de AFD\u2019s
Como ja´ foi dito, sempre existe um AFD m\u131´nimo equivalente a um AFD. M\u131´nimo, no
sentido de que na\u2dco existe nenhum outro com menor nu´mero de estados.
Definic¸a\u2dco 5 Um AFDM e´ dito ser um AFD m\u131´nimo para a linguagem L(M) se nenhum
AFD para L(M) conte´m menor nu´mero de estados que M .
Pela Definic¸a\u2dco 5, nenhum AFD que contenha estados na\u2dco alcanc¸a´veis a partir do
estado inicial pode ser m\u131´nimo. Assim, um primeiro passo para obter um AFD m\u131´nimo
e´ a eliminac¸a\u2dco pura e simples destes estados. Em seguida, deve-se determinar grupos de
estados equivalentes , no sentido ditado pela Definic¸a\u2dco 6 abaixo, e substituir cada grupo
por um u´nico estado.
Definic¸a\u2dco 6 Seja um AFD M = (E,\u3a3, \u3b4, i, F ). Dois estados e, e\u2032 \u2208 E sa\u2dco ditos equiva-
lentes, e \u2248 e\u2032, se, e somente se:
para todo y \u2208 \u3a3\u2217, \u3b4\u2c6(e, y) \u2208 F se, e somente se, \u3b4\u2c6(e\u2032, y) \u2208 F .
Pode-se mostrar que a relac¸a\u2dco \u201c\u2248\u201d, definida acima, e´ de fato uma relac¸a\u2dco de equi-
vale\u2c6ncia, ou seja, uma relac¸a\u2dco reflexiva, sime´trica e transitiva.
Dada a Definic¸a\u2dco 6, durante o processamento de uma palavra, tanto faz atingir e como
e\u2032: um sufixo y sera´ reconhecido passando-se por e se, e somente se, ele for reconhecido
passando-se por e\u2032. O que justifica eliminar um dos estados e substituir toda refere\u2c6ncia
a ele por refere\u2c6ncias ao outro. Ou seja, se [e] = {e1, e2, . . . , en} e´ a classe de equivale\u2c6ncia
de e na partic¸a\u2dco induzida por \u2248, os estados e1, e2, . . . , en podem ser substitu´\u131dos por um
u´nico estado.
Por outro lado, se os estados e e e\u2032 na\u2dco sa\u2dco equivalentes no sentido da Definic¸a\u2dco 6, ou
seja, se e 6\u2248 e\u2032 (equivalentemente, [e] 6= [e\u2032]), enta\u2dco e´ porque existe uma palavra y \u2208 \u3a3\u2217
para a qual:
\u3b4\u2c6(e, y) \u2208 F e \u3b4\u2c6(e\u2032, y) 6\u2208 F , ou vice-versa.
Neste caso, atingir e pode significar o reconhecimento de uma palavra e atingir e\u2032 pode
significar o na\u2dco reconhecimento da palavra: basta que o sufixo restante da palavra seja
70
y. Assim, se tanto e quanto e\u2032 sa\u2dco alcanc¸a´veis a partir do estado inicial, os dois estados
na\u2dco podem ser reduzidos a um u´nico.
Na definic¸a\u2dco a seguir, mostra-se como construir um auto\u2c6mato m\u131´nimo equivalente a
um AFDM , dadas as classes de equivale\u2c6ncia induzidas pela relac¸a\u2dco\u2248. Na\u2dco sera´ mostrado
formalmente que um auto\u2c6mato reduzido, como esta´ la´ definido, e´ um auto\u2c6mato m\u131´nimo.
Para os propo´sitos deste texto sa\u2dco suficientes as evide\u2c6ncias apontadas na argumentac¸a\u2dco
acima mais o resultado do Teorema 2, apresentado abaixo.
Definic¸a\u2dco 7 Seja um AFD M = (E,\u3a3, \u3b4, i, F ). Um auto\u2c6mato reduzido correspondente
a M e´ o AFD M \u2032 = (E \u2032,\u3a3, \u3b4\u2032, i\u2032, F \u2032), onde:
\u2022 E \u2032 = {[e] | e \u2208 E};
\u2022 \u3b4\u2032([e], a) = [\u3b4(e, a)] para todo