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
Em seguida,
elimina-se um a um os estados do diagrama ER, com excec¸a\u2dco de i e fk. Para que um estado
e possa ser eliminado, \u201csimula-se\u201d todas as passagens por e poss´\u131veis: para cada par de
estados [e1, e2] tais que ha´ transic¸a\u2dco de e1 para e e transic¸a\u2dco de e para e2 (e1 e e2 podem
ser o mesmo estado, mas nenhum deles pode ser e), produz-se uma transic¸a\u2dco de e1 para
e2, como ilustra a Figura 2.31. Durante todo o processo, e´ interessante manter apenas
uma transic¸a\u2dco de um ve´rtice para outro. Para isto, se ha´ transic¸o\u2dces de e para e\u2032 sob s1,
s2, . . . , sm, substitui-se todas elas por uma so´ transic¸a\u2dco de e para e
\u2032 sob s1+s2+ · · ·+sm.
Apo´s eliminados todos os estados em E \u2212 {i, fk}, chega-se a uma das situac¸o\u2dces ba´sicas
mostradas na Figura 2.32. Como esta´ la´ mostrado, a ER final para rk sera´ da forma r
\u2217
ou q\u2217r(s+ tq\u2217r)\u2217. Neste u´ltimo caso, quaisquer uma das 4 transic¸o\u2dces do diagrama ER da
figura 2.32(b) pode estar ausente; basta, enta\u2dco, substituir a ER correspondente na ER
q\u2217r(s+ tq\u2217r)\u2217 por \u2205 e simplificar; exemplo: se as transic¸o\u2dces de i para i sob q e de fk para
115
Entrada: um AFD M = (E,\u3a3, \u3b4, i, {f1, f2, . . . , fn}).
Sa´\u131da: uma ER que denota L(M).
seja o diagrama ER D ide\u2c6ntico ao diagrama de estados de M ;
/* Aqui, considere que se na\u2dco existe a tal que \u3b4(e, a) = e\u2032,
no diagrama ER ha´ uma transic¸a\u2dco de e para e\u2032 sob \u2205. */
para cada par [e1, e2] \u2208 E × E fac¸a
sejam (todas) as transic¸o\u2dces de e1 para e2 sob s1, s2, . . . , sm em D;
se m > 1 enta\u2dco
substitua todas por uma sob s1 + s2 + · · ·+ sm
fimse
fimpara;
para k de 1 ate´ n fac¸a
seja o diagrama ER ide\u2c6ntico a D, mas com apenas fk como estado final;
para cada e \u2208 E \u2212 {i, fk} fac¸a
para cada par [e1, e2] \u2208 E × E, e1 6= e e e2 6= e fac¸a
sejam s, r1, r2 e r3 tais que:
. ha´ transic¸a\u2dco de e1 para e2 sob s,
. ha´ transic¸a\u2dco de e1 para e sob r1,
. ha´ transic¸a\u2dco de e para e sob r2,
. ha´ transic¸a\u2dco de e para e2 sob r3;
substitua a transic¸a\u2dco de e1 para e2 sob s
por uma transic¸a\u2dco de e1 para e2 sob s+ r1r
\u2217
2r3
fimpara;
elimine e;
fimpara;
se i = fk enta\u2dco
pk \u2190 r\u2217, conforme Figura 2.32(a)
sena\u2dco
pk \u2190 q\u2217r(s+ tq\u2217r)\u2217, conforme Figura 2.32(b)
fimse
fimpara;
retorne p1 + p2 + · · ·+ pn
Figura 2.33: Algoritmo AF \u2192 ER.
i sob t na\u2dco existirem, a ER simplificada sera´: \u2205\u2217r(s+ \u2205q\u2217r)\u2217 = rs\u2217. Veja o Exerc´\u131cio 6 no
final desta sec¸a\u2dco.
A prova do Teorema 13 e´ o esboc¸o de um algoritmo para obtenc¸a\u2dco de uma ER que
denota a linguagem reconhecida por um AFD. A seguir, tal esboc¸o e´ tomado como base
para a concretizac¸a\u2dco de um algoritmo. Para propiciar a obtenc¸a\u2dco de um algoritmo mais
conciso e simples, sera´ assumido, para um diagrama ER, que, se na\u2dco ha´ transic¸a\u2dco de um
estado e para um estado e\u2032 (que podem ser o mesmo estado), enta\u2dco \u201cha´ uma transic¸a\u2dco de
e para e\u2032 sob \u2205\u201d. E´ evidente que o efeito, em ambos os casos, e´ o mesmo. Entretanto, tal
suposic¸a\u2dco serve apenas para simplificar a apresentac¸a\u2dco do algoritmo; em uma aplicac¸a\u2dco
do mesmo, ou em uma implementac¸a\u2dco, pode ser mais conveniente trabalhar sem tal
suposic¸a\u2dco. Neste u´ltimo caso, as alterac¸o\u2dces requeridas, embora um pouco trabalhosas,
sa\u2dco triviais. Na Figura 2.33 esta´ mostrado o algoritmo.
116
-
\ufffd\ufffd\ufffd
p0 -b \ufffd\ufffd\ufffd
\ufffd
\ufffd	i1
?
a
6
a\ufffd\ufffd\ufffd
i0 -b \ufffd\ufffd\ufffd
p1?
a
6
a
@
@R
b\ufffd\ufffd\ufffd
e
\ufffd
\ufffd\ufffd
b
\ufffd\ufffd\ufb00 a,b
(a) Diagrama de estados
-
\ufffd\ufffd\ufffd
p0 -b \ufffd\ufffd\ufffd
\ufffd
\ufffd	i1
?
a
6
a\ufffd\ufffd\ufffd
i0 -b \ufffd\ufffd\ufffd
p1?
a
6
a
@
@R
b\ufffd\ufffd\ufffd
e
\ufffd
\ufffd\ufffd
b
\ufffd\ufffd\ufb00 a+ b
(b) Diagrama ER
-
\ufffd\ufffd\ufffd
p0 -b \ufffd\ufffd\ufffd
\ufffd
\ufffd	i1
?
a
6
a\ufffd\ufffd\ufffd
i0 -b \ufffd\ufffd\ufffd
p1?
a
6
a
(c) Eliminando e
-
\ufffd\ufffd\ufffd
p0 -b \ufffd\ufffd\ufffd
\ufffd
\ufffd	i1
\ufffd\ufffd
?
aa
@
@
@@R
ab \ufffd\ufffd\ufffd
p1?
a
6
a
(d) Eliminando i0
-
\ufffd\ufffd\ufffd
p0 -b+ aba\ufffd\ufffd\ufffd
\ufffd
\ufffd	i1
\ufffd\ufffd
?
aa \ufffd\ufffd
?
aa
(e) Eliminando p1
Figura 2.34: Determinando uma ER a partir de AFD.
Exemplo 86 Seja o diagrama de estados mostrado na Figura 2.34(a), de um AFD que
reconhece a linguagem {w \u2208 {a, b}\u2217 | |w| e´ \u131´mpar e w conte´m exatamente um b}. Apo´s o
primeiro comando para do algoritmo da Figura 2.33, tem-se o diagrama ER mostrado na
Figura 2.34(b). No presente caso, sera´ obtido apenas p1, pois ha´ apenas um estado final.
Para isto, o algoritmo elimina os estados: e, i0 e p1 (qualquer ordem serve). Supondo
que a eliminac¸a\u2dco ocorre nesta ordem, tem-se:
1) Eliminando e. Como na\u2dco existe transic¸a\u2dco de e para algum e2 diferente de e
(comando para mais interno), ele e´ simplesmente eliminado (apo´s este para mais
interno). Resultado: Figura 2.34(c).
2) Eliminando i0. Existem dois pares [e1, e2] que promovem efetivamente mudanc¸as
no para mais interno: [p0, p0] e [p0, p1]. Assim, antes de eliminar i0, introduz-se:
\u2022 uma transic¸a\u2dco de p0 para p0 sob \u2205+ a\u2205\u2217a = aa;
\u2022 uma transic¸a\u2dco de p0 para p1 sob \u2205+ a\u2205\u2217b = ab.
Resultado: Figura 2.34(d).
3) Eliminando p1. Existem dois pares [e1, e2] que promovem efetivamente mudanc¸as
no para mais interno: [p0, i1] e [i1, i1]. Assim, antes de eliminar p1, introduz-se:
\u2022 uma transic¸a\u2dco de p0 para i1 sob b+ ab\u2205\u2217a = b+ aba (substituindo a anterior,
sob b);
\u2022 uma transic¸a\u2dco de i1 para i1 sob \u2205+ a\u2205\u2217a = aa.
Resultado: Figura 2.34(e).
Tem-se, enta\u2dco a ER determinada: (aa)\u2217(b+ aba)(aa)\u2217.
117
No exemplo 86, a ER obtida reflete de forma bastante clara a linguagem que ela
denota. Infelizmente, na maior parte dos casos a ER obtida pelo processo do algoritmo
da Figura 2.33 e´ grande e ileg´\u131vel. Por outro lado, ela e´ correta e pode ser manipulada,
utilizando-se as equivale\u2c6ncias da Tabela 2.1 (pa´gina 112) e outras, para se chegar a uma
ER mais conveniente.
Uma pequena alterac¸a\u2dco no algoritmo da Figura 2.33 aumenta a eficie\u2c6ncia do mesmo
quando ha´ mais de um estado final: logo apo´s o primeiro comando para, atribuir a D o
diagrama ER resultante da eliminac¸a\u2dco de todos os estados em E \u2212{f1, f2, . . . , fn}\u2212 {i}.
Com isto, no comando para seguinte, para cada estado final fk, sera\u2dco eliminados apenas
os estados fi tais que i 6= k.
Exerc´\u131cios
1. Retire o ma´ximo de pare\u2c6nteses das ER\u2019s seguintes, sem alterar seus significados:
(a) ((0 + ((0 + 1)0)) + (11)).
(b) (((00) + (1(11\u2217)))\u2217((01)((01)(0 + 1)))).
2. Descreva, em portugue\u2c6s, as linguagens sobre {0, 1} denotadas pelas seguintes ER\u2019s:
(a) 0(0 + 1)\u22171.
(b) 0\u2217(0 + 1)1\u2217.
(c) (0 + 1)\u22171(0 + 1)(0 + 1).
(d) (0 + \u3bb)(10 + 1)\u2217.
3. Encontre (diretamente) expresso\u2dces regulares que denotem os seguintes conjuntos:
(a) {w \u2208 {a, b}\u2217 | |w| \u2265 3}.
(b) {w \u2208 {a, b}\u2217 | w comec¸a com a e tem tamanho par}.
(c) {w \u2208 {a, b}\u2217 | w tem nu´mero par de a\u2019s}.
(d) {w \u2208 {a, b}\u2217 | w conte´m bb}.
(e) {w \u2208 {a, b}\u2217 | w conte´m exatamente um bb}.
(f) {w \u2208 {a, b}\u2217 | w conte´m apenas um ou dois b\u2019s}.
(g) {w \u2208 {a, b, c}\u2217 | o nu´mero de a\u2019s e/ou b\u2019s e´ par}.
(h) {w \u2208 {a, b, c}\u2217 | w na\u2dco termina com cc}.
4. Simplifique as ER\u2019s a seguir. Procure usar as equivale\u2c6ncias da Tabela 2.1. Se
precisar de alguma equivale\u2c6ncia na\u2dco presente na Tabela 2.1, explicite-a e justifique
sua validade (mesmo que informalmente).
(a) \u2205\u2217 + \u3bb\u2217.
(b) 0\u2217 + 1\u2217 + 0\u22171\u2217 + (0 + 1)\u2217.
(c) (0 + 00)\u2217(1 + 01).
118
(d) (0 + 01)\u2217(0\u22171\u2217 + 1)\u2217.
(e) ((00 + 01 + 10 + 11)\u2217(0 + 1))\u2217.
(f) (0 + 1)\u22170(0 + 1)\u22171(0 + 1)\u2217.
5. Construa um AFD para cada uma das linguagens denotadas pelas ER\u2019s:
(a) (ab)\u2217ac.
(b) (ab)\u2217(ba)\u2217.
(c) (ab\u2217a)\u2217(ba\u2217b)\u2217.
(d) (aa+ b)\u2217baab.
(e) ((aa+ bb)\u2217cc)\u2217.
6. Considere o diagrama ER da Figura 2.32(b), pa´gina 115. Simplifique a ER cor-
respondente, q\u2217r(s + tq\u2217r)\u2217, para todas as 24 possibilidades de se atribuir \u2205 a`s
expresso\u2dces ba´sicas q, r, s e t.
7. Construa uma ER que denote a linguagem reconhecida pelo AFD M , definido
abaixo, utilizando o me´todo do algoritmo da Figura 2.33, pa´gina 116:
M = ({0, 1, 2, 3}, {a, b}, \u3b4, 0, {2}), sendo \u3b4 dada por:
\u3b4 a b
0 1 3
1 0 2
2 3 1
3 3 3
8. Obtenha ER\u2019s que denotem as seguintes linguagens sobre {0, 1}, a partir de um
AFD para as mesmas, usando o algoritmo da Figura 2.33, pa´gina 116:
(a) O conjunto das palavras de tamanho maior que 1 tais que os 0\u2019s (se houver
algum) precedem os 1\u2019s (se houver algum).
(b) O conjunto das palavras que comec¸am com 1 e terminam com 1.
(c) O conjunto das palavras que comec¸am com 1, terminam com 1 e te\u2c6m pelo
menos um 0.