introdução aos fundamentos da computação solucionário
Soluções para a tarefa
Resposta:pm(L): (E\u2032,\u3a3, \u3b4\u2032, I \u2032, F \u2032), onde:
\u2022 E\u2032 = E × E;
\u2022 I \u2032 = I × F ;
\u2022 para cada (e1, e2) \u2208 E\u2032 e a \u2208 \u3a3:
\u3b4\u2032([e1, e2], a) = {[e\u20321, e\u20322] | e\u20321 \u2208 \u3b4(e1, a) e e2 \u2208 \u3b4(e\u20322, b) para algum b \u2208 \u3a3}; e
\u2022 F \u2032 = {[e, e] | e \u2208 E}.
h) Sejam dois AFNsM1 = (E1,\u3a3, \u3b41, I1, F1) eM2 = (E2,\u3a3, \u3b42, I2, F2) tais que L(M1) =
L1 e L(M2) = L2. (E´ sempre poss´\u131vel, e trivial, tornar os alfabetos ide\u2c6nticos sem
alterar as linguagens.) Um AFN M3 = (E3,\u3a3, \u3b43, I3, F3) que reconhece \u3be\u2c6(L1, L2) e´
tal que:
68
\u2022 E3 = E1 × E2;
\u2022 I3 = I1 × I2;
\u2022 para cada (e1, e2) \u2208 E3 e a \u2208 \u3a3:
\u3b43([e1, e2], a) = {[e\u20321, e2] | e\u20321 \u2208 \u3b41(e1, a)} \u222a {[e1, e\u20322] | e\u20322 \u2208 \u3b42(e2, a)}; e
\u2022 F3 = F1 × F2.
15. Seja um AFN M = (E,\u3a3, \u3b4, i, F ). Um AFD M \u2032 equivalente sem transic¸o\u2dces para o estado
inicial: M \u2032 = (E \u222a {i\u2032},\u3a3, \u3b4\u2032, i\u2032, F \u2032), tal que i\u2032 6\u2208 E, \u3b4\u2032(e, a) = \u3b4(e, a) para todo e \u2208 E e
todo a \u2208 \u3a3, \u3b4\u2032(i\u2032, a) = \u3b4(i, a) para todo a \u2208 \u3a3, e F \u2032 = F se i 6\u2208 F , e F \u2032 = F \u222a{i\u2032} se i \u2208 F .
16. a) Por induc¸a\u2dco sobre n. Primeiro, observe que se L1 e L2 sa\u2dco regulares, L1\u222aL2 e´ regular,
pois as linguagens regulares sa\u2dco fechadas sob unia\u2dco. Seja n \u2265 2 e n linguagens
regulares L1, L2, . . . , Ln. Suponha, como hipo´tese de induc¸a\u2dco, que
\u22c3
2\u2264i\u2264n Li seja
regular. Dada essa hipo´tese e o fato de que as linguagens regulares sa\u2dco fechadas sob
unia\u2dco, segue-se que \u22c3
2\u2264i\u2264n+1
Li = (
\u22c3
2\u2264i\u2264n
Li) \u222a Ln+1
e´ regular.
b) Cada linguagem {aibi}, para i \u2265 2, e´ uma linguagem regular, mas\u22c3
i\u22652
{aibi} = {aibi | i \u2265 2}
na\u2dco e´.
17. (\u2192) Suponha que L \u222a {\u3bb} e´ regular. Como (L \u222a {\u3bb}) \u2212 {\u3bb} = L \u2212 {\u3bb} e as linguagens
regulares sa\u2dco fechadas sob diferenc¸a, L\u2212 {\u3bb} e´ regular.
(\u2192) Suponha que L \u2212 {\u3bb} e´ regular. Como (L \u2212 {\u3bb}) \u222a {\u3bb} = L \u222a {\u3bb} e as linguagens
regulares sa\u2dco fechadas sob unia\u2dco, L \u222a {\u3bb} e´ regular.
18. Seja r uma expressa\u2dco regular que denota L. Seja r\u2032 a expressa\u2dco regular obtida de r
substituindo-se cada s´\u131mbolo do alfabeto, a, de r por h(a). Mostra-se facilmente, por
induc¸a\u2dco a partir da definic¸a\u2dco de expressa\u2dco regular, que r\u2032 denota h(L).
Agora, para provar o fechamento sob homorfismo inverso, seja um AFD para L, M =
(E,\u3a3, \u3b4, i, F ). Seja o AFD M \u2032 = (E,\u3a3, \u3b4\u2032, i, F ) em que \u3b4\u2032(e, a) = \u3b4\u2c6(e, h(a)) para todo
e \u2208 E e a \u2208 \u3a3. Pode-se provar, por induc¸a\u2dco sobre |w|, que \u3b4\u2032(e, w) = \u3b4\u2c6(e, h(w)). Como
os estados iniciais e finais dos dois AFDs sa\u2dco os mesmos, segue-se que w \u2208 L(M \u2032) se, e
somente se, h(w) \u2208 L(M) e, portanto, L(M \u2032) = h\u22121(L).
19. Seja L = {anbn |n \u2265 0} e h : {anb} \u2192 {1} tal que h(a) = \u3bb e h(b) = 1. Segue-que que
h(L) = {1}\u2217 e, assim, h(L) e´ regular, embora L na\u2dco seja.
20. Para cada a \u2208 \u3a3, seja er(a) uma expressa\u2dco regular que denota s(a) (que existe, pois s(a)
e´ regular). Seja r uma expressa\u2dco regular que denota L. Seja r\u2032 a expressa\u2dco regular obtida
de r substituindo-se cada s´\u131mbolo do alfabeto, a, de r por er(a). Mostra-se facilmente,
por induc¸a\u2dco a partir da definic¸a\u2dco de expressa\u2dco regular, que r\u2032 denota s(L).
21. Seja um AFD M = (E,\u3a3, \u3b4, i, F ) que reconhec¸a L1. Um AFD que reconhece L1/L2 e´ o
AFD M \u2032 = (E,\u3a3, \u3b4, i, F \u2032), cuja u´nica diferenc¸a com relac¸a\u2dco a M1 e´ o conjunto de estados
finais, assim definido: F \u2032 = {e \u2208 E | \u2203y \u2208 L2\u3b4\u2c6(e, y) \u2208 F}.
69
22. a) Suponha que L \u222a F seja regular. F \u2212 L tambe´m e´ regular, pois e´ finita. Logo,
seu complemento, F \u2212 L, tambe´m e´ regular. Como a intersec¸a\u2dco de duas linguagens
regulares e´ regular, segue-se que (L\u222aF )\u2229F \u2212 L e´ regular. Mas, (L\u222aF )\u2229F \u2212 L = L,
que na\u2dco e´ regular. Contradic¸a\u2dco. Portanto, L \u222a F na\u2dco e´ regular.
b) Suponha que L \u2212 F seja regular. F \u2229 L tambe´m e´ regular, pois e´ finita. Como a
unia\u2dco de duas linguagens regulares e´ regular, segue-se que (L\u2212F )\u222a(F \u2229L) e´ regular.