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
dos estados de X utilizando-se apenas
transic¸o\u2dces sob \u3bb. Observe que uma transic¸a\u2dco sob \u3bb ocorre sem consumo de s´\u131mbolo algum;
assim, a func¸a\u2dco fecho \u3bb aplicada a X, da´ todos os estados alcanc¸a´veis a partir dos estados
de X sem consumo de s´\u131mbolos.
Definic¸a\u2dco 14 Seja um auto\u2c6mato finito na\u2dco determin´\u131stico com transic¸o\u2dces \u3bb M = (E,\u3a3, \u3b4, I, F ).
A func¸a\u2dco fecho \u3bb para M , f\u3bb, e´ uma func¸a\u2dco de P(E) para P(E), definida recursivamente
como segue:
(a) X \u2286 f\u3bb(X);
(b) se e \u2208 f\u3bb(X) enta\u2dco \u3b4(e, \u3bb) \u2286 f\u3bb(X).
Segue a definic¸a\u2dco de \u3b4\u2c6 para AFN\u3bb\u2019s.
91
AFD para L1
-
\ufffd\ufffd\ufffd\ufffd\ufffd\ufffd\ufffd
p0
\ufffd\ufffd
?
1
-
0
\ufb00 0 \ufffd\ufffd\ufffd\ufffdi0
\ufffd\ufffd
?
1
AFD para L2
-
\ufffd\ufffd\ufffd\ufffdp1
\ufffd\ufffd
?
0
-
1
\ufb00 1 \ufffd\ufffd\ufffd\ufffd\ufffd\ufffd\ufffd
i1
\ufffd\ufffd
?
0
AFN\u3bb para L1L2
-
\ufffd\ufffd\ufffd\ufffdp0
\ufffd\ufffd
?
1
-
0
\ufb00 0 \ufffd\ufffd\ufffd\ufffdi0
\ufffd\ufffd
?
1
\ufffd \ufffd6
\u3bb
\ufffd\ufffd\ufffd\ufffdp1
\ufffd\ufffd
?
0
-
1
\ufb00 1 \ufffd\ufffd\ufffd\ufffd\ufffd\ufffd\ufffd
i1
\ufffd\ufffd
?
0
Figura 2.20: AFN\u3bb para L1L2
Definic¸a\u2dco 15 Seja um AFN\u3bb M = (E,\u3a3, \u3b4, I, F ). A func¸a\u2dco de transic¸a\u2dco estendida, \u3b4\u2c6,
e´ uma func¸a\u2dco de P(E)× \u3a3\u2217 para P(E), definida recursivamente como segue:
(a) \u3b4\u2c6(\u2205, w) = \u2205, para todo w \u2208 \u3a3\u2217;
(b) \u3b4\u2c6(A, \u3bb) = f\u3bb(A), para A \u2286 E;
(c) \u3b4\u2c6(A, ay) = \u3b4\u2c6(
\u22c3
e\u2208f\u3bb(A) \u3b4(e, a), y), para A \u2286 E, a \u2208 \u3a3 e y \u2208 \u3a3\u2217.
Segue um exemplo de AFN\u3bb .
Exemplo 68 Dados dois AFN\u2019s M1 e M2, pode-se construir um AFN\u3bb que reconhece
L(M1)L(M2) simplesmente colocando-se uma transic¸a\u2dco sob \u3bb de cada estado final de M1
para cada estado inicial de M2; os estados iniciais do AFN\u3bb seriam os estados iniciais de
M1, e os estados finais seriam os estados finais de M2. Seja, por exemplo, o problema de
construir um auto\u2c6mato para reconhecer L = L1L2, onde L1 = {w \u2208 {0, 1}\u2217 | w tem um
nu´mero par de 0\u2019s} e L2 = {w \u2208 {0, 1}\u2217 | w tem um nu´mero \u131´mpar de 1\u2019s}. Construir
diretamente um AFD (ou mesmo um AFN comum) para L na\u2dco e´ trivial. No entanto, e´
extremamente fa´cil obter AFD\u2019s para L1 e L2 e, em seguida, um AFN\u3bb para L a partir
destes, como mostra o diagrama de estados da Figura 2.20.
Para obter um AFN equivalente a um AFN\u3bb, basta \u201celiminar\u201d as transic¸o\u2dces \u3bb, o que
pode ser feito facilmente com o aux´\u131lio da func¸a\u2dco f\u3bb, como sera´ visto em seguida.
Teorema 8 Para qualquer AFN\u3bb existe um AFN equivalente.
Prova
Seja um AFN\u3bbM = (E,\u3a3, \u3b4, I, F ). Um AFN equivalente aM seriaM \u2032 = (E,\u3a3, \u3b4\u2032, I \u2032, F ),
onde:
\u2022 I \u2032 = f\u3bb(I); e
92
\u2022 \u3b4\u2032(e, a) = f\u3bb(\u3b4(e, a)), para cada e \u2208 E e a \u2208 \u3a3.
Para provar que L(M \u2032) = L(M), e´ suficiente mostrar que
\u3b4\u2c6\u2032(f\u3bb(X), w) = \u3b4\u2c6(X,w) para todo X \u2286 E e w \u2208 \u3a3\u2217 (2.3)
pois, em particular, ter-se-a´ que:
\u3b4\u2c6\u2032(I \u2032, w)= \u3b4\u2c6\u2032(f\u3bb(I), w) pela definic¸a\u2dco de I \u2032
= \u3b4\u2c6(I, w) por 2.3.
Sera´ mostrado, enta\u2dco, que 2.3 e´ verdadeira, por induc¸a\u2dco sobre |w|. Para w = \u3bb, tem-se:
\u3b4\u2c6\u2032(f\u3bb(X), \u3bb) = f\u3bb(X) pela Definic¸a\u2dco 10
= \u3b4\u2c6(X,\u3bb) pela Definic¸a\u2dco 15.
Suponha que \u3b4\u2c6\u2032(f\u3bb(X), y) = \u3b4\u2c6(X, y) para y \u2208 \u3a3\u2217. Basta provar, enta\u2dco, que \u3b4\u2c6\u2032(f\u3bb(X), ay) =
\u3b4\u2c6(X, ay) para a \u2208 \u3a3. De fato:
\u3b4\u2c6\u2032(f\u3bb(X), ay) = \u3b4\u2c6\u2032(
\u22c3
e\u2208f\u3bb(X) \u3b4
\u2032(e, a), y) pela Definic¸a\u2dco 10
= \u3b4\u2c6\u2032(
\u22c3
e\u2208f\u3bb(X) f\u3bb(\u3b4(e, a)), y) pela Definic¸a\u2dco de \u3b4
\u2032
= \u3b4\u2c6\u2032(f\u3bb(
\u22c3
e\u2208f\u3bb(X) \u3b4(e, a)), y) pelo exerc´\u131cio 13
= \u3b4\u2c6(
\u22c3
e\u2208f\u3bb(X) \u3b4(e, a), y) pela hipo´tese de induc¸a\u2dco
= \u3b4\u2c6(X, ay) pela Definic¸a\u2dco 15.
Seguem exemplos de obtenc¸a\u2dco de AFN\u2019s a partir de AFN\u3bb\u2019s utilizando-se o me´todo
apresentado na prova do Teorema 8.
Exemplo 69 Na Figura 2.21 esta\u2dco mostrados (a) o AFN\u3bb equivalente ao AFNE da
Figura 2.19 (pa´gina 91), apo´s a eliminac¸a\u2dco das transic¸o\u2dces sob 00 e 11, e (b) o AFN obtido
apo´s a eliminac¸a\u2dco da transic¸a\u2dco \u3bb. Note que o AFN tem como estados iniciais f\u3bb({1}) =
{1, 2}, e que \u3b4\u2032(e, a) = \u3b4(e, a) para a \u2208 \u3a3, pois, para este exemplo, f\u3bb(\u3b4(e, a)) = \u3b4(e, a)
para todo (e, a) \u2208 E × \u3a3.
Assim, por exemplo, para se obter um AFD equivalente a um auto\u2c6mato finito na\u2dco
determin´\u131stico estendido, basta obter um AFN equivalente, como acima, e depois obter
um AFD equivalente ao AFN.
Exemplo 70 Na Figura 2.22 esta´ mostrado o diagrama de estados de um AFN equiva-
lente ao AFN\u3bb do Exemplo 68 (Figura 2.20, pa´gina 92). Existem apenas duas transic¸o\u2dces
para as quais f\u3bb(\u3b4(e, a)) 6= \u3b4(e, a): a de i0 para p0 sob 0, e a de p0 para p0 sob 1.
Elas originam, enta\u2dco as seguintes transic¸o\u2dces no AFN resultante (conforme a prova do
Teorema 8):
\u3b4\u2032(i0, 0) = f\u3bb(\u3b4(i0, 0))
= f\u3bb({p0})
= {p0, p1}.
93
(a) AFN\u3bb
-
\ufffd\ufffd\ufffd\ufffd1 \ufffd
\ufffd
\ufffd
\ufffd\ufffd\ufffd
\u3bb
@
@
@
@@R
1
\ufffd\ufffd\ufffd\ufffd\ufffd\ufffd\ufffd
2 -0
\ufffd\ufffd\ufffd\ufffd2\u2032\ufb00 0
\ufffd\ufffd\ufffd\ufffd\ufffd\ufffd\ufffd
3 -1
\ufffd\ufffd\ufffd\ufffd3\u2032\ufb00 1
(b) AFN
-
\ufffd\ufffd\ufffd\ufffd1 @
@
@
@@R
1
-
\ufffd\ufffd\ufffd\ufffd\ufffd\ufffd\ufffd
2 -0
\ufffd\ufffd\ufffd\ufffd2\u2032\ufb00 0
\ufffd\ufffd\ufffd\ufffd\ufffd\ufffd\ufffd
3 -1
\ufffd\ufffd\ufffd\ufffd3\u2032\ufb00 1
Figura 2.21: AFN equivalente a AFNE da Figura 2.19
-
\ufffd\ufffd\ufffd\ufffdp0
\ufffd\ufffd
?
1
-
0
\ufb00 0 \ufffd\ufffd\ufffd\ufffdi0
\ufffd\ufffd
?
1
-0
\ufffd \ufffd61
-
\ufffd\ufffd\ufffd\ufffdp1
\ufffd\ufffd
?
0
-
1
\ufb00 1 \ufffd\ufffd\ufffd\ufffd\ufffd\ufffd\ufffd
i1
\ufffd\ufffd
?
0
Figura 2.22: AFN para AFN\u3bb do Exemplo 68.
-e´ um caso especial de
\ufb00 pode ser transformado em
'
&
$
%AFD
\ufffd \ufffd
?
\ufffd\ufffd6
'
&
$
%AFN
\ufffd \ufffd
?
\ufffd\ufffd6
'
&
$
%AFN\u3bb
\ufffd \ufffd
?
\ufffd\ufffd6
'
&
$
%AFNE
Figura 2.23: Relac¸o\u2dces entre auto\u2c6matos finitos
94
\u3b4\u2032(p0, 1) = f\u3bb(\u3b4(p0, 1))
= f\u3bb({p0})
= {p0, p1}.
A Figura 2.23 sumariza as relac¸o\u2dces entre os diversos tipos de auto\u2c6matos ja´ vistos.
Daqui para frente sera´ utilizada a denominac¸a\u2dco \u201cauto\u2c6mato finito\u201d (AF) para englobar
AFD\u2019s, AFN\u2019s, AFNE\u2019s e AFN\u3bb\u2019s.
Definic¸a\u2dco 16 Uma linguagem e´ dita ser uma linguagem regular (ou linguagem de estado-
finito4, ou ainda, conjunto regular) se existe um auto\u2c6mato finito que a reconhece.
Que caracter´\u131sticas interessantes dos pontos de vista teo´rico e pra´tico te\u2c6m as lingua-
gens regulares? Como identificar se uma linguagem e´ regular? Estes assuntos, ja´ tocados
de leve, sa\u2dco tratados na Sec¸a\u2dco 2.4.
Exerc´\u131cios
1. Construa AFN\u2019s para as seguintes linguagens sobre {a, b, c}:
(a) O conjunto das palavras com, no m\u131´nimo, 3 ocorre\u2c6ncias de abc.
(b) O conjunto das palavras com, no m\u131´nimo, 3 ocorre\u2c6ncias de a\u2019s ou 3 ocorre\u2c6ncias
de b\u2019s ou 3 ocorre\u2c6ncias de c\u2019s .
(c) O conjunto das palavras com sufixo abc ou bca.
(d) O conjunto das palavras em que existem duas ocorre\u2c6ncias de abc com um
nu´mero \u131´mpar de s´\u131mbolos entre elas.
(e) O conjunto das palavras em que o u´ltimo s´\u131mbolo seja ide\u2c6ntico ao primeiro.
(f) O conjunto das palavras em que o u´ltimo s´\u131mbolo seja diferente do primeiro.
(g) O conjunto das palavras em que o u´ltimo s´\u131mbolo tenha ocorrido antes.
(h) O conjunto das palavras em que o u´ltimo s´\u131mbolo tenha ocorrido antes no
ma´ximo uma vez.
(i) O conjunto das palavras em que o u´ltimo s´\u131mbolo na\u2dco tenha ocorrido antes.
2. Sejam as linguagens da forma Ln = {xyx | x, y \u2208 {a, b}\u2217 e |x| = n}. Determine o
menor nu´mero de estados para um AFN e para um AFD que reconhec¸am Ln, nos
seguintes casos:
(a) n = 1.
(b) n = 2.
(c) n arbitra´rio.
4Finite-state language.
95
3. Seja um AFN M = (E,\u3a3, \u3b4, I, F ). Sejam X1, X2, . . . , Xn tais que Xi 6= \u2205 para
1 \u2264 i \u2264 n. Prove que, para qualquer w \u2208 \u3a3\u2217, \u3b4\u2c6(\u22c3ni=1Xi, w) = \u22c3ni=1 \u3b4\u2c6(Xi, w).
4. Mostre que para todo AFN existe um AFN equivalente com um u´nico estado inicial.
5. Seja o AFN M = ({1, 2, 3}, {a, b}, \u3b4, {1}, {1, 2, 3}), onde \u3b4 e´ dada por:
\u3b4 a b
1 {2} {}
2 {3} {}
3 {} {3}
Obtenha um AFN com um u´nico estado final equivalente a M .
6. Mostre que sim ou na\u2dco: para todo AFN existe um AFN equivalente com um u´nico
estado final.
7. Seja o AFN\u3bb M = ({0, 1, 2}, {a, b, c}, \u3b4, 0, {2}), sendo \u3b4 dada por:
\u3b4 a b c \u3bb
0 {0} \u2205 \u2205 {1}
1 \u2205 {1} \u2205 {2}
2 \u2205 \u2205 {2} \u2205
(a) Determine f\u3bb(e) para e = 0, 1, 2.
(b) Determine um AFN M \u2032 equivalente a M , usando a te´cnica do Teorema 8.
(c) Determine um AFD equivalente a M \u2032, usando a te´cnica do Teorema 7 .
8. Obtenha um AFD equivalente ao AFN cujo diagrama de estados esta´ mostrado na
Figura 2.21(b), pa´gina 94, usando a te´cnica do Teorema 7.
9. Obtenha um AFD equivalente ao AFN cujo diagrama de estados esta´ mostrado na
Figura 2.22, pa´gina 94, usando a te´cnica do Teorema 7.
10. Construa AFNE\u2019s para as linguagens do Exerc´\u131cio 1, com um m\u131´nimo de transic¸o\u2dces
poss´\u131vel.
11. Defina uma func¸a\u2dco \u3b4\u2c6 para AFNE, de tal forma que \u3b4\u2c6(X,w), onde X e´ um conjunto
de estados, seja o conjunto de todos os estados alcanc¸a´veis a partir dos estados de
X consumindo-se w.
12. Na prova do Teorema 4 mostrou-se como construir um AFD para reconhecer a unia\u2dco
das linguagens reconhecidas por dois AFD\u2019s. Suponha