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
| dZ2
E \u2192 c
* Z1 \u2192 bD | bZ1D | bDZ1 | bZ1DZ1
* Z2 \u2192 cBD | cBDZ2
3.4.4 GLC\u2019s e auto\u2c6matos com pilha
Nesta sec¸a\u2dco, mostra-se que GLC\u2019s e AP\u2019s reconhecem a mesma classe de linguagens, qual
seja a classe das linguagens livres do contexto.
No teorema a seguir, mostra-se que para qualquer GLC G existe um AP, de apenas
dois estados, que reconhece L(G).
Teorema 26 Para qualquer GLC G existe um AP que reconhece L(G).
Prova
Seja G\u2032 = (V,\u3a3, R, P ) uma GLC na FNG equivalente a G. Um APN que aceita L(G\u2032)
e´ M = ({i, f},\u3a3, V, \u3b4, {i}, {f}), onde \u3b4 consta das transic¸o\u2dces:
\u2022 \u3b4(i, \u3bb, \u3bb) = {[f, P ]};
\u2022 se P \u2192 \u3bb \u2208 R, \u3b4(f, \u3bb, P ) = {[f, \u3bb]}; e
\u2022 para cada a \u2208 \u3a3 e cada X \u2208 V , \u3b4(f, a,X) = {[f, y] | y \u2208 V \u2217 e X \u2192 ay \u2208 R}.
Para provar que L(M) = L(G\u2032), basta mostrar que para todo x \u2208 \u3a3\u2217 e y \u2208 V \u2217, P \u2217\u21d2 xy
se, e somente se, [i, x, \u3bb]
\u2217` [f, \u3bb, y], pois quando y = \u3bb, seguir-se-a´ que para todo x \u2208 \u3a3\u2217,
P
\u2217\u21d2 x se, e somente se, [i, x, \u3bb] \u2217` [f, \u3bb, \u3bb].
(\u2192)
Sera´ provado, por induc¸a\u2dco sobre n, que para todo n \u2265 1, todo x \u2208 \u3a3\u2217 e y \u2208 V \u2217, se
P
n\u21d2 xy enta\u2dco [i, x, \u3bb] \u2217` [f, \u3bb, y]. Para n = 1, tem-se dois casos: P 1\u21d2 \u3bb (x = y = \u3bb) e,
portanto, P \u2192 \u3bb \u2208 R, ou P 1\u21d2 ay (x = a) e, portanto, P \u2192 ay \u2208 R. Para o primeiro
caso tem-se, pela definic¸a\u2dco de \u3b4, que [i, \u3bb, \u3bb] ` [f, \u3bb, P ] ` [f, \u3bb, \u3bb]. E para o segundo caso,
tem-se que [i, a, \u3bb] ` [f, a, P ] ` [f, \u3bb, y].
Seja um n \u2265 1 arbitra´rio, e suponha, como hipo´tese de induc¸a\u2dco, que para todo x \u2208 \u3a3\u2217
e todo y \u2208 V \u2217, se P n\u21d2 xy enta\u2dco [i, x, \u3bb] \u2217` [f, \u3bb, y]. Suponha enta\u2dco que P n+1\u21d2 xay para
y \u2208 V \u2217. Tem-se, enta\u2dco, que ou P n\u21d2 xaPy \u21d2 xay com aplicac¸a\u2dco da regra P \u2192 \u3bb no
u´ltimo passo, ou enta\u2dco P
n\u21d2 xXu \u21d2 xazu, onde X \u2192 az \u2208 R e y = zu. No primeiro
caso, tem-se que [i, xa, \u3bb]
\u2217` [f, \u3bb, Py] pela hipo´tese de induc¸a\u2dco; e, pela definic¸a\u2dco de \u3b4,
183
tem-se que [f, \u3bb, Py] ` [f, \u3bb, y]; logo, [i, xa, \u3bb] \u2217` [f, \u3bb, y], como requerido. No segundo
caso, pela hipo´tese de induc¸a\u2dco, [i, x, \u3bb]
\u2217` [f, \u3bb,Xu], e, portanto, [i, xa, \u3bb] \u2217` [f, a,Xu];
como X \u2192 az \u2208 R, [f, a,Xu] ` [f, \u3bb, zu]; e como y = zu, segue-se finalmente que
[i, xa, \u3bb]
\u2217` [f, \u3bb, y].
(\u2190)
Esta parte pode ser provada de forma ana´loga a` anterior.
A seguir, apresenta-se um exemplo de aplicac¸a\u2dco do me´todo apresentado na prova do
Teorema 26, de obtenc¸a\u2dco de AP\u2019s a partir de GLC\u2019s.
Exemplo 116 Seja a GLC do Exemplo 103, pa´gina 157, G = ({P}, {0, 1}, R, P ), onde
R consta das regras:
P \u2192 0P1P | 1P0P | \u3bb
Uma GLC equivalente na FNG seria aquela com as regras:
P \u2192 0PUP | 1PZP | \u3bb
Z \u2192 0
U \u2192 1
Um AP que reconhece L(G) seria enta\u2dco ({i, f}, {0, 1}, {P,Z, U}, \u3b4, i, {f}), onde \u3b4 e´ dada
por:
\u3b4(i, \u3bb, \u3bb) = {[f, P ]}
\u3b4(f, \u3bb, P ) = {[f, \u3bb]}
\u3b4(f, 0, P ) = {[f, PUP ]}
\u3b4(f, 1, P ) = {[f, PZP ]}
\u3b4(f, 0, Z) = {[f, \u3bb]}
\u3b4(f, 1, U) = {[f, \u3bb]}.
O Exemplo 116 apresenta mais uma soluc¸a\u2dco alternativa para o mesmo problema que
ja´ teve soluc¸o\u2dces exibidas nas Figuras 3.5 (pa´gina 143), 3.9 (pa´gina 150) e 3.10 (pa´gina
150).
Para completar, mostra-se a seguir que e´ sempre poss´\u131vel obter uma GLC que gera a
linguagem reconhecida por um AP. Antes, pore´m, sera´ apresentada a ide´ia central relativa
ao processo de obter a GLC a partir do AP.
Seja um APN M = (E,\u3a3,\u393, \u3b4, I, F ). Dados dois estados e, e\u2032 \u2208 E e A \u2208 \u393\u222a{\u3bb}, con-
sidere o conjunto C(e, A, e\u2032) de todas as palavras w \u2208 \u3a3\u2217 tais que o APN M , comec¸ando
em e, com a pilha contendo A, termina no estado e\u2032 com a pilha vazia, apo´s consumir w,
ou seja,
C(e, A, e\u2032) = {w \u2208 \u3a3\u2217 | [e, w,A] \u2217` [e\u2032, \u3bb, \u3bb]}.
184
Observe que
L(M) =
\u22c3
(i,f)\u2208I×F
C(i, \u3bb, f).
Suponha que seja poss´\u131vel gerar o conjunto C(e, A, e\u2032) por meio de uma GLC cuja varia´vel
de partida seja [e, A, e\u2032]. Enta\u2dco L(M) pode ser gerada por uma GLC constitu´\u131da de todas
as regras [e, A, e\u2032], mais as regras da forma P \u2192 [i, \u3bb, f ], para cada i \u2208 I e f \u2208 F . A
prova do teorema a seguir apresenta os detalhes.
Teorema 27 Para qualquer APN M existe uma GLC que gera L(M).
Prova
Seja um APN M = (E,\u3a3,\u393, \u3b4, I, F ). Como discutido acima, sera´ mostrado como
construir uma GLC com varia´veis da forma [e, A, e\u2032], para e, e\u2032 \u2208 E e A \u2208 \u393 \u222a {\u3bb}, de
modo que para todo w \u2208 \u3a3\u2217,
[e, A, e\u2032]
\u2217\u21d2 w se, e somente se, [e, w,A] \u2217` [e\u2032, \u3bb, \u3bb].
A grama´tica G tal que L(G) = L(M) sera´ (V,\u3a3, R, P ), onde V = {P}\u222aE×(\u393\u222a{\u3bb})×E
e R conte´m as regras:
\u2022 para cada i \u2208 I e cada f \u2208 F , P \u2192 [i, \u3bb, f ];
\u2022 para cada e \u2208 E, [e, \u3bb, e]\u2192 \u3bb;
e tambe´m, para cada transic¸a\u2dco [e\u2032, z] \u2208 \u3b4(e, a, A), onde a \u2208 \u3a3 \u222a {\u3bb}, z = B1B2 . . . Bn
(Bi \u2208 \u393) e A \u2208 \u393 \u222a {\u3bb}, as seguintes regras (tipo 1):
\u2022 se z = \u3bb, [e, A, d]\u2192 a[e\u2032, \u3bb, d] para cada d \u2208 E;
\u2022 se z 6= \u3bb, [e, A, dn]\u2192 a[e\u2032, B1, d1] . . . [dn\u22121, Bn, dn] para cada d1, d2, . . . , dn \u2208 E.
Ainda, se A = \u3bb, tem-se, adicionalmente (tipo 2):
\u2022 se z = \u3bb, [e, C, d]\u2192 a[e\u2032, C, d] para cada C \u2208 \u393 e cada d \u2208 E;
\u2022 se z 6= \u3bb, [e, C, dn+1] \u2192 a[e\u2032, B1, d1] . . . [dn\u22121, Bn, dn][dn, C, dn+1] para cada C \u2208 \u393 e
cada d1, d2, . . . , dn, dn+1 \u2208 E.
Dada a discussa\u2dco anterior, para concluir a prova basta mostrar que
[e, A, e\u2032]
\u2217\u21d2 w se, e somente se, [e, w,A] \u2217` [e\u2032, \u3bb, \u3bb]
para todo e, e\u2032 \u2208 E, A \u2208 \u393 \u222a {\u3bb} e w \u2208 \u3a3\u2217, o que e´ deixado como exerc´\u131cio.
Exemplo 117 Seja o APD cujo diagrama de estados esta´ mostrado na Figura 3.26, que
reconhece {ancbn | n \u2265 0}\u222a{\u3bb}. Utilizando o me´todo delineado no Teorema 27, obte´m-se
inicialmente as regras:
\u2022 P \u2192 [0, \u3bb, 0] | [0, \u3bb, 1]
185
-
\ufffd\ufffd\ufffd\ufffd\ufffd\ufffd\ufffd
0
\ufffd\ufffd
?
a, \u3bb/X
-
c, \u3bb/\u3bb \ufffd\ufffd\ufffd\ufffd\ufffd\ufffd\ufffd
1
\ufffd\ufffd
?
b, X/\u3bb
Figura 3.26: APD para {ancbn | n \u2265 0} \u222a {\u3bb}.
\u2022 [0, \u3bb, 0]\u2192 \u3bb
[1, \u3bb, 1]\u2192 \u3bb
A seguir, vem as regras restantes, um grupo delas para cada transic¸a\u2dco do APD:
\u2022 para a transic¸a\u2dco [0, X] \u2208 \u3b4(0, a, \u3bb):
Tipo 1:
[0, \u3bb, 0]\u2192 a[0, X, 0]
[0, \u3bb, 1]\u2192 a[0, X, 1]
Tipo 2:
[0, X, 0]\u2192 a[0, X, 0][0, X, 0] | a[0, X, 1][1, X, 0]
[0, X, 1]\u2192 a[0, X, 0][0, X, 1] | a[0, X, 1][1, X, 1]
\u2022 para a transic¸a\u2dco [1, \u3bb] \u2208 \u3b4(0, c, \u3bb):
Tipo 1:
[0, \u3bb, 0]\u2192 c[1, \u3bb, 0]
[0, \u3bb, 1]\u2192 c[1, \u3bb, 1]
Tipo 2:
[0, X, 0]\u2192 c[1, X, 0]
[0, X, 1]\u2192 c[1, X, 1]
\u2022 para a transic¸a\u2dco [1, \u3bb] \u2208 \u3b4(1, b, X):
Tipo 1:
[1, X, 0]\u2192 b[1, \u3bb, 0]
[1, X, 1]\u2192 b[1, \u3bb, 1]
Eliminando-se as varia´veis inu´teis, obte´m-se as seguintes regras:
P \u2192 [0, \u3bb, 0] | [0, \u3bb, 1]
[0, \u3bb, 1]\u2192 a[0, X, 1] | c[1, \u3bb, 1]
[0, X, 1]\u2192 a[0, X, 1][1, X, 1] | c[1, X, 1]
[1, X, 1]\u2192 b[1, \u3bb, 1]
186
[0, \u3bb, 0]\u2192 \u3bb
[1, \u3bb, 1]\u2192 \u3bb
O me´todo descrito na prova do Teorema 27 pode gerar muitas varia´veis (e, portanto,
regras) inu´teis, como evidenciado no Exemplo 117. Isto pode ser, pelo menos em grande
parte, evitado observando-se que para uma varia´vel [e, A, e\u2032] ser u´til e´ necessa´rio que
exista um caminho de e para e\u2032 no diagrama de estados do AP, e que seja poss´\u131vel
desempilhar o que for empilhado em alguma computac¸a\u2dco iniciando em e e terminando
em e\u2032. Observando-se o diagrama de estados da Figura 3.26, ve\u2c6-se claramente que sa\u2dco
inu´teis varia´veis como:
\u2022 [0, X, 0]: na\u2dco e´ poss´\u131vel desempilhar X em um caminho que comece e termine em 0;
\u2022 [1, X, 0]: na\u2dco ha´ caminho de 1 para 0.
Exerc´\u131cios
1. Construa GLC\u2019s para as linguagens do Exerc´\u131cio 3 do final da Sec¸a\u2dco 3.3, pa´gina 155.
2. Construa GLC\u2019s para as linguagens:
(a) {ambnc3m+2n+1 | m,n \u2265 0}.
(b) {anb2n+kc3k | n, k \u2265 0}.
(c) {ambnck | n > m+ k}.
3. Construa GLC\u2019s para:
(a) L1 = {0n1k | 2n \u2264 k \u2264 3n}.
(b) L2 = {anbkcm | k = 2n+m}.
(c) (L1 \u222a L2)2.
4. Seja G a grama´tica:
P \u2192 AB
A \u2192 aAb | c
B \u2192 bBc | a
(a) Construa uma derivac¸a\u2dco mais a esquerda de acbbbacc.
(b) Construa a a´rvore de derivac¸a\u2dco para a derivac¸a\u2dco constru´\u131da em (a).
(c) Defina L(G) utilizando notac¸a\u2dco de conjunto.
5. Seja a grama´tica G:
P \u2192 aPb | aaPb | \u3bb
187
(a) Mostre que G e´ amb´\u131gua.
(b) Construa uma grama´tica na\u2dco amb´\u131gua equivalente a G.
6. Existe GLC amb´\u131gu¨a, sem varia´veis inu´teis, que gere {\u3bb}? e {0}?
7. Seja G uma GLC que contenha, dentre outras, as regras:
\u3008cmd\u3009 \u2192 se \u3008exp-rel\u3009 enta\u2dco \u3008cmd\u3009
\u3008cmd\u3009 \u2192 se \u3008exp-rel\u3009 enta\u2dco \u3008cmd\u3009 sena\u2dco \u3008cmd\u3009
onde \u3008cmd\u3009 e \u3008exp-rel\u3009 sa\u2dco varia´veis u´teis e se, enta\u2dco e sena\u2dco sa\u2dco terminais. Mostre
que G e´ amb´\u131gu¨a. Como eliminar a ambigu¨idade causada por tais regras?
8. Construa uma grama´tica sem