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
de MooreM = (E,\u3a3,\u2206, \u3b4, \u3c3, i) para
a palavra w \u2208 \u3a3\u2217 e´ r(i, w).
Dado um AFD M = (E,\u3a3, \u3b4, i, F ) e´ poss´\u131vel constuir uma ma´quina de Moore M \u2032 =
(E,\u3a3,\u2206, \u3b4, \u3c3, i) tal que:
w \u2208 L(M) se, e somente se, P (r(i, w)),
onde P e´ uma propriedade bem definida. Com isto, pode-se dizer que qualquer AFD
pode ser \u201csimulado\u201d por meio de ma´quina de Moore. Uma possibilidade e´ fazer:
\u2022 \u2206 = {0, 1}; e
\u2022 \u3c3(e) = 1 se e \u2208 F , e \u3c3(e) = 0 se e 6\u2208 F .
Tem-se, com isto, que:
w \u2208 L(M) se, e somente se, r(i, w) termina em 1.
O diagrama de estados de uma ma´quina de Moore e´ similar ao de um AFD. A u´nica
diferenc¸a e´ que cada ve´rtice, ao inve´s de representar um estado, representa um estado e
a sa´\u131da correspondente. Assim, a transic¸a\u2dco \u3b4(e, a) = e\u2032 e´ representada assim, juntamente
com \u3c3(e) e \u3c3(e\u2032):
104
-
\ufffd\ufffd \ufffd\ufffd00/0
\ufffd\ufffd
?
0
\ufffd\ufffd
\ufffd\ufffd
\ufffd\ufffd
\ufffd*
1
\ufffd\ufffd \ufffd\ufffd01/1
?
0
6
1
HH
HH
HH
HY
0 \ufffd\ufffd \ufffd\ufffd10/1
HHHHHHHj
1 \ufffd\ufffd \ufffd\ufffd11/2
\ufffd\ufffd
?
1
\ufffd\ufffd\ufffd\ufffd\ufffd\ufffd\ufffd\ufffd
0
Figura 2.26: Uma Ma´quina de Moore.
\ufffd\ufffd \ufffd\ufffde/\u3c3(e) -a \ufffd\ufffd \ufffd\ufffde\u2032/\u3c3(e\u2032)
Exemplo 77 Na Figura 2.26 esta´ mostrado o diagrama de estados para uma ma´quina de
Moore que determina o nu´mero de 1\u2019s presentes nos dois u´ltimos d´\u131gitos de uma palavra
de {0, 1}\u2217. No caso, tal nu´mero e´ dado pelo u´ltimo s´\u131mbolo da palavra de sa´\u131da. Por
exemplo:
r(00, 1110) = 0r(01, 110)
= 01r(11, 10)
= 012r(11, 0)
= 0122r(10, \u3bb)
= 01221.
Uma ma´quina de Mealy e´ um AFD com um s´\u131mbolo de sa´\u131da associado a cada
transic¸a\u2dco, como definido a seguir.
Definic¸a\u2dco 20 Uma ma´quina de Mealy e´ uma se\u2c6xtupla (E,\u3a3,\u2206, \u3b4, \u3c3, i), onde:
\u2022 E (o conjunto de estados), \u3a3 (o alfabeto de entrada), \u3b4 (a func¸a\u2dco de transic¸a\u2dco) e i
(o estado inicial) sa\u2dco como em AFD\u2019s;
\u2022 \u2206 e´ o alfabeto de sa´\u131da;
\u2022 \u3c3 : E × \u3a3\u2192 \u2206 e´ a func¸a\u2dco de sa´\u131da, uma func¸a\u2dco total.
Seja uma transic¸a\u2dco \u3b4(e, a) = e\u2032 e a sa´\u131da \u3c3(e, a) = d (e, e\u2032 \u2208 E, a \u2208 \u3a3, d \u2208 \u2206). Tal
transic¸a\u2dco sera´ dita ser uma transic¸a\u2dco de e para e\u2032 sob a/d. Ela e´ representada em um
diagrama de estados da seguinte maneira:
\ufffd\ufffd\ufffd\ufffde -a/d \ufffd\ufffd\ufffd\ufffde\u2032
105
como exemplifica a Figura 2.3, na pa´gina 61.
Assim como uma ma´quina de Moore, uma ma´quina de Mealy e´ similar a um AFD,
a diferenc¸a sendo tambe´m que, ao inve´s de aceitac¸a\u2dco ou rejeic¸a\u2dco, existira´ uma palavra
de sa´\u131da. No caso, esta e´ inicializada com \u3bb e, ao ser efetuada uma transic¸a\u2dco para um
estado e sob a/d, d e´ concatenada a` direita dela.
A seguir sera´ definida a func¸a\u2dco s : E × \u3a3\u2217 :\u2192 \u2206\u2217, onde s(e, w) e´ a palavra de sa´\u131da
emitida pela ma´quina de Mealy para a palavra de entrada w, quando a ma´quina e´ iniciada
no estado e.
Definic¸a\u2dco 21 Seja uma ma´quina de Mealy M = (E,\u3a3,\u2206, \u3b4, \u3c3, i). A func¸a\u2dco de sa´\u131da
estendida para M , s : E × \u3a3\u2217 \u2192 \u2206\u2217, e´ definida recursivamente como segue:
(a) s(e, \u3bb) = \u3bb;
(b) s(e, ay) = \u3c3(e, a)s(\u3b4(e, a), y), para todo a \u2208 \u3a3 e y \u2208 \u3a3\u2217.
Define-se, com isto, a sa´\u131da de uma ma´quina de Mealy.
Definic¸a\u2dco 22 A sa´\u131da computada por uma ma´quina de MealyM = (E,\u3a3,\u2206, \u3b4, \u3c3, i) para
a palavra w \u2208 \u3a3\u2217 e´ s(i, w).
A ma´quina de Mealy apresentada na Sec¸a\u2dco 2.1.3, cujo diagrama de estados esta´ mos-
trado na Figura 2.3, pa´gina 61, seria enta\u2dco uma se\u2c6xtupla
({1, 2 \u2191, 2 \u2193, 3},P({1, 2, 3}), {\u2191, \u2193, \u25e6}, \u3b4, \u3c3, 1)
onde \u3b4 e \u3c3 sa\u2dco dadas por (na linha e, coluna a, esta´ o par \u3b4(e, a)/\u3c3(e, a)):
\u3b4/\u3c3 \u2205 {1} {2} {3} {1, 2} {1, 3} {2, 3} {1, 2, 3}
1 1/\u25e6 1/\u25e6 2 \u2191 / \u2191 2 \u2191 / \u2191 1/\u25e6 1/\u25e6 2 \u2191 / \u2191 1/\u25e6
2 \u2191 2 \u2191 /\u25e6 1/ \u2193 2 \u2191 /\u25e6 3/ \u2191 2 \u2191 /\u25e6 3/ \u2191 2 \u2191 /\u25e6 2 \u2191 /\u25e6
2 \u2193 2 \u2193 /\u25e6 1/ \u2193 2 \u2193 /\u25e6 3/ \u2191 2 \u2193 /\u25e6 1/ \u2193 2 \u2193 /\u25e6 2 \u2193 /\u25e6
3 3/\u25e6 2 \u2193 / \u2193 2 \u2193 / \u2193 3/\u25e6 2 \u2193 / \u2193 3/\u25e6 3/\u25e6 3/\u25e6
Exemplo 78 Na Figura 2.2, pa´gina 60, foi mostrado um diagrama de estados para um
AFD que determina se um nu´mero em notac¸a\u2dco bina´ria e´ divis´\u131vel por 6. Tal AFD pode
ser complementado para se tornar uma ma´quina de Mealy que determina tambe´m o
quociente da divisa\u2dco. Seja x \u2208 {0, 1}\u2217, e sejam q1 e r1 o quociente e o resto da divisa\u2dco de
\u3b7(x) por 6, onde \u3b7(x) e´ o nu´mero representado por x. Assim, \u3b7(x) = 6q1 + r1. Supondo
que apo´s x vem outro s´\u131mbolo a \u2208 {0, 1}, sejam q2 e r2 o quociente e o resto da divisa\u2dco
de \u3b7(xa) por 6. Tem-se dois casos a considerar:
\u2022 a = 0. Neste caso, tem-se que \u3b7(x0) = 2\u3b7(x) = 6q2 + r2 e, portanto, 2(6q1 + r1) =
6q2 + r2. Assim, q2 = 2q1 + (2r1 \u2212 r2)/6.
\u2022 a = 1. Neste caso, \u3b7(x1) = 2\u3b7(x)+1 = 6q2+r2 e, portanto, 2(6q1+r1)+1 = 6q2+r2.
Assim, q2 = 2q1 + (2r1 + 1\u2212 r2)/6.
106
-
\ufffd\ufffd\ufffd\ufffd0
\ufffd\ufffd
?
0/0
\ufffd
\ufffd
\ufffd
\ufffd\ufffd1/0
\ufffd\ufffd\ufffd\ufffd1
@
@
@
@I
0/1 \ufffd\ufffd\ufffd\ufffd3
-0/0
\ufffd\ufffd\ufffd\ufffd2
\ufb00
1/1
\ufffd\ufffd\ufffd\ufffd4
@
@
@
@R
1/0
\ufffd
\ufffd
\ufffd
\ufffd	 0/1
\ufffd\ufffd\ufffd\ufffd5
\ufffd\ufffd
?
1/1
?
1/0
6
1/1
?
0/0
6
0/1
Figura 2.27: Ma´quina de Mealy para Bina´rio Mo´dulo 6.
Veja, enta\u2dco, que se o pro´ximo d´\u131gito da palavra de entrada e´ 0, o pro´ximo d´\u131gito do
quociente e´ dado por (2r1 \u2212 r2)/6, e se o pro´ximo d´\u131gito da palavra de entrada e´ 1, o
pro´ximo d´\u131gito do quociente e´ dado por (2r1 \u2212 r2 + 1)/6. Com isto, obte´m-se a ma´quina
mostrada na Figura 2.27.
Note que esta ma´quina da´, ale´m do quociente (via as transic¸o\u2dces), tambe´m o resto (via
os estados). Pode-se dizer, no caso, que se tem \u201cduas ma´quinas em uma\u201d, uma de Mealy
(para o quociente) e outra de Moore (para o resto).
Estritamente falando, pode na\u2dco haver uma ma´quina de Mealy equivalente a uma
ma´quina de Moore: para uma ma´quina de Moore de estado inicial i, r(i, \u3bb) = \u3c3(i), que
pode na\u2dco ser \u3bb, enquanto que, para uma ma´quina de Mealy de estado inicial i\u2032, s(i\u2032, \u3bb)
e´ sempre \u3bb! Assim, na definic¸a\u2dco de equivale\u2c6ncia abaixo, na\u2dco se leva em conta a sa´\u131da da
ma´quina de Moore para o prefixo \u3bb da palavra de entrada.
Definic¸a\u2dco 23 Uma ma´quina de Moore (E1,\u3a3,\u2206, \u3b41, \u3c31, i1) e uma ma´quina de Mealy
(E2,\u3a3,\u2206, \u3b42, \u3c32, i2) sa\u2dco ditas equivalentes se, para todo w \u2208 \u3a3\u2217, r(i1, w) = \u3c31(i1)s(i2, w).
O teorema a seguir mostra como obter uma ma´quina de Mealy equivalente a uma
ma´quina de Moore.
Teorema 10 Para toda ma´quina de Moore existe uma ma´quina de Mealy equivalente.
Prova
Seja uma ma´quina de Moore M = (E,\u3a3,\u2206, \u3b4, \u3c3, i). Uma ma´quina de Mealy equiva-
lente e´ M \u2032 = (E,\u3a3,\u2206, \u3b4, \u3c3\u2032, i), onde para cada e \u2208 E e a \u2208 \u3a3, \u3c3\u2032(e, a) = \u3c3(\u3b4(e, a)). Sera´
mostrado, por induc¸a\u2dco sobre |w|, que r(e, w) = \u3c3(e)s(e, w) para e \u2208 E arbitra´rio. Com
isto, conclui-se, em particular, que r(i, w) = \u3c3(i)s(i, w).
Para w = \u3bb tem-se:
r(e, \u3bb)= \u3c3(e) pela definic¸a\u2dco de r
= \u3c3(e)\u3bb
= \u3c3(e)s(e, \u3bb) pela definic¸a\u2dco de s.
Suponha, como hipo´tese de induc¸a\u2dco, que r(e, y) = \u3c3(e)s(e, y), para y \u2208 \u3a3\u2217 tal que |y| = n.
Seja uma palavra de tamanho n+ 1, w = ay, a \u2208 \u3a3. Enta\u2dco:
107
-
\ufffd\ufffd \ufffd\ufffd00
\ufffd\ufffd
?
0/0
\ufffd\ufffd
\ufffd\ufffd
\ufffd\ufffd
\ufffd*
1/1
\ufffd\ufffd \ufffd\ufffd01
?
0/1
6
1/1
HH
HH
HH
HY
0/0 \ufffd\ufffd \ufffd\ufffd10
HHHHHHHj
1/2 \ufffd\ufffd \ufffd\ufffd11
\ufffd\ufffd
?
1/2
\ufffd\ufffd\ufffd\ufffd\ufffd\ufffd\ufffd\ufffd 0/1
Figura 2.28: Uma Ma´quina de Mealy obtida de uma Ma´quina de Moore.
r(e, ay)= \u3c3(e)r(\u3b4(e, a), y) pela definic¸a\u2dco de r
= \u3c3(e)\u3c3(\u3b4(e, a))s(\u3b4(e, a), y) pela hipo´tese de induc¸a\u2dco
= \u3c3(e)\u3c3\u2032(e, a)s(\u3b4(e, a), y) pela definic¸a\u2dco de \u3c3\u2032
= \u3c3(e)s(e, ay) pela definic¸a\u2dco de s.
Segue um exemplo de aplicac¸a\u2dco da te´cnica descrita na prova do Teorema 10.
Exemplo 79 Na Figura 2.28 esta´ o diagrama de estados da ma´quina de Mealy equiva-
lente a` ma´quina de Moore do Exemplo 77, pa´gina 105, obtida de acordo com a te´cnica
descrita na prova do Teorema 10.
A seguir, o Teorema 11 mostra como obter uma ma´quina de Moore equivalente a uma
ma´quina de Mealy dada.
Teorema 11 Para toda ma´quina de Mealy existe uma ma´quina de Moore equivalente.
Prova
Seja uma ma´quina de Mealy M = (E,\u3a3,\u2206, \u3b4, \u3c3, i). Uma ma´quina de Moore equiva-
lente seria M \u2032 = (E \u2032,\u3a3,\u2206, \u3b4\u2032, \u3c3\u2032, i\u2032), onde:
\u2022 i\u2032 = [i, d0] para um certo d0 \u2208 \u2206 (qualquer um serve);
\u2022 E \u2032 = {[\u3b4(e, a), \u3c3(e, a)] | e \u2208 E e a \u2208 \u3a3} \u222a {i\u2032};
\u2022 \u3b4\u2032([e, d], a) = [\u3b4(e, a), \u3c3(e, a)] para cada [e, d] \u2208 E \u2032 e a \u2208 \u3a3;
\u2022 \u3c3\u2032([e, d]) = d para cada e \u2208 E e d \u2208 \u2206.
Para provar a equivale\u2c6ncia entre M e M \u2032, deve-se mostrar que r([i, d0], w) = d0s(i, w)
para todo w \u2208 \u3a3\u2217. Isto segue do resultado mais geral r([e, d], w) = ds(e, w) para todo
[e, d] \u2208 E \u2032 e w \u2208 \u3a3\u2217, que sera´ provado a seguir, por induc¸a\u2dco sobre |w|.
Seja [e, d] \u2208 E \u2032 arbitra´rio. No caso em que |w| = 0, tem-se que:
r([e, d], \u3bb)= \u3c3\u2032([e, d]) pela definic¸a\u2dco de r
= d pela definic¸a\u2dco