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
sa\u2dco mais curtas.
Por exemplo, aa tem a seguinte derivac¸a\u2dco em G:
P \u21d2 ABA (regra P \u2192 ABA)
\u21d2 aBA (regra A\u2192 a)
\u21d2 aA (regra B \u2192 \u3bb)
\u21d2 aa (regra A\u2192 a).
E a mesma palavra tem a seguinte derivac¸a\u2dco em G\u2032:
P \u21d2 aBa (regra P \u2192 aBa)
\u21d2 aa (regra B \u2192 \u3bb).
Existem duas formas normais especialmente importantes para GLC\u2019s: as formas nor-
mais de Chomsky e de Greibach, que sera\u2dco definidas mais abaixo. Um passo comum para
a obtenc¸a\u2dco de uma grama´tica em uma destas formas, que seja equivalente a um GLC
dada, G, e´ a obtenc¸a\u2dco de uma grama´tica G\u2032, equivalente a G, que so´ tenha regras das
formas:
169
Entrada: uma GLC G = (V,\u3a3, R, P );
Sa´\u131da: {X \u2208 V | X \u2217\u21d2 \u3bb}.
A \u2190 \u2205;
repita
N \u2190 {Y 6\u2208 A | Y \u2192 z \u2208 R e z \u2208 A\u2217};
A \u2190 A\u222aN
ate´ N = \u2205;
retorne A.
Figura 3.21: Algoritmo para determinar varia´veis anula´veis.
\u2022 P \u2192 \u3bb, somente no caso em que \u3bb \u2208 L(G) e P e´ o s´\u131mbolo de partida de G\u2032;
\u2022 X \u2192 w, w 6= \u3bb, somente nos casos em que w \u2208 \u3a3 ou |w| > 1.
Em outras palavras, G\u2032 na\u2dco pode ter regras \u3bb, exceto se \u3bb \u2208 L(G) (e neste caso tem a
regra P \u2192 \u3bb), e na\u2dco pode ter regras unita´rias7, que sa\u2dco regras da forma X \u2192 Y , onde
X e Y sa\u2dco varia´veis. A seguir sera´ mostrado, primeiramente, como eliminar as regras \u3bb
de uma GLC sem alterar a linguagem gerada. Em seguida, sera´ mostrado como eliminar
as regras unita´rias.
Um corola´rio do Teorema 18 e´ o fato de que qualquer regra \u3bb pode ser eliminada,
com excec¸a\u2dco da regra P \u2192 \u3bb, onde P e´ o s´\u131mbolo de partida. Mas, ao se eliminar uma
regra \u3bb usando-se o me´todo do Teorema 18, pode-se criar outras regras \u3bb. O teorema
apresentado a seguir mostra uma te´cnica para eliminar todas as regras \u3bb, preservando-se
ou criando-se a regra P \u2192 \u3bb no caso em que \u3bb \u2208 L(G).
O me´todo a ser introduzido no teorema a seguir utiliza o conceito de varia´vel anula´vel .
Uma varia´velX e´ dita ser anula´vel em uma GLCG se, e somente se,X
\u2217\u21d2G \u3bb. O algoritmo
da Figura 3.21 determina o conjunto das varia´veis anula´veis de uma GLC.
Teorema 19 Para qualquer GLC existe uma GLC equivalente cuja u´nica regra \u3bb, se
houver, e´ P \u2192 \u3bb, onde P e´ o s´\u131mbolo de partida.
Prova
Seja uma GLC G = (V,\u3a3, R, P ). Seja a GLC G\u2032 = (V,\u3a3, R\u2032, P ) onde R\u2032 e´ obtido
assim:
(1) para cada regra Y \u2192 z \u2208 R, para cada forma de escrever z como x1X1x2 . . . Xnxn+1,
onde n \u2265 0, xi \u2208 (V \u222a \u3a3)\u2217, x1x2 . . . xn+1 6= \u3bb e Xi e´ varia´vel anula´vel, coloque a
regra Y \u2192 x1x2 . . . xn+1 em R\u2032;
(2) se P for anula´vel, coloque P \u2192 \u3bb em R\u2032.
Analisando-se estas duas etapas da construc¸a\u2dco de G\u2032, ve\u2c6-se que G\u2032 na\u2dco conte´m regra \u3bb,
exceto no caso em que P e´ anula´vel, ou seja, P
\u2217\u21d2G \u3bb, ou ainda, \u3bb \u2208 L(G). Assim, para
provar o teorema, basta provar que P
\u2217\u21d2G w se, e somente P \u2217\u21d2G\u2032 w para todo w \u2208 \u3a3\u2217
tal que w 6= \u3bb. Mas isto segue do fato de que para todo X \u2208 V , X \u2217\u21d2G w se, e somente
X
\u2217\u21d2G\u2032 w para todo w \u2208 \u3a3\u2217 tal que w 6= \u3bb, resultado este que sera´ provado a seguir.
7Unit rules ou chain rules.
170
(\u2192)
Sera´ mostrado, inicialmente, por induc¸a\u2dco sobre n, que para todo n \u2265 1, para todo
X \u2208 V e todo w \u2208 \u3a3\u2217 tal que w 6= \u3bb, se X n\u21d2G w enta\u2dco X \u2217\u21d2G\u2032 w.
Sejam X \u2208 V e w \u2208 \u3a3\u2217 tal que w 6= \u3bb, arbitra´rios, e suponha que X 1\u21d2G w. Tem-se,
enta\u2dco, que X \u2192 w \u2208 R. Como w 6= \u3bb, pela definic¸a\u2dco de R\u2032 X \u2192 w \u2208 R\u2032 e, portanto,
X
1\u21d2G\u2032 w. Seja n \u2265 1 arbitra´rio, e suponha, como hipo´tese de induc¸a\u2dco, que se X n\u21d2G w
enta\u2dco X
\u2217\u21d2G\u2032 w para todo X \u2208 V e todo w \u2208 \u3a3\u2217 tal que w 6= \u3bb. Suponha agora que
X
n+1\u21d2 G w para X \u2208 V e w \u2208 \u3a3\u2217 tal que w 6= \u3bb, arbitra´rios. Neste caso,
X
1\u21d2G Y1Y2 . . . Yk n\u21d2G w = x1x2 . . . xk,
onde Yi
pi\u21d2G xi, para cada 1 \u2264 i \u2264 k, sendo pi \u2264 n. Para cada xi: se xi = \u3bb e Yi
e´ uma varia´vel, enta\u2dco Yi e´ uma varia´vel anula´vel; e se xi 6= \u3bb, enta\u2dco, pela hipo´tese de
induc¸a\u2dco, tem-se que Yi
\u2217\u21d2G\u2032 xi. E como G tem a regra X \u2192 Y1Y2 . . . Yk, G\u2032 tem a regra
X \u2192 Z1Z2 . . . Zk, onde Zi = Yi se xi 6= \u3bb, e Zi = \u3bb se xi = \u3bb. Assim sendo, tem-se,
finalmente, que:
X
1\u21d2G\u2032 Z1Z2 . . . Zk \u2217\u21d2G\u2032 x1Z2 . . . Zk \u2217\u21d2G\u2032 x1x2 . . . Zk \u2217\u21d2G\u2032 x1x2 . . . xk.
(\u2190)
Sera´ mostrado, tambe´m por induc¸a\u2dco sobre n, que para todo n \u2265 1, para todo X \u2208 V
e todo w \u2208 \u3a3\u2217 tal que w 6= \u3bb, se X n\u21d2G\u2032 w enta\u2dco X \u2217\u21d2G w.
Sejam X \u2208 V e w \u2208 \u3a3\u2217 tal que w 6= \u3bb, arbitra´rios, e suponha que X 1\u21d2G\u2032 w. Tem-se,
enta\u2dco, que X \u2192 w \u2208 R\u2032. Como w 6= \u3bb, pela definic¸a\u2dco de R\u2032 existe y tal que |y| > 0
e X \u2192 y \u2208 R\u2032 e w e´ o resultado de substituir zero ou mais ocorre\u2c6ncias de varia´veis
anula´veis de y por \u3bb. Assim sendo, tem-se que X
1\u21d2G y \u2217\u21d2G w. Seja n \u2265 1 arbitra´rio, e
suponha, como hipo´tese de induc¸a\u2dco, que se X
n\u21d2G\u2032 w enta\u2dco X \u2217\u21d2G w para todo X \u2208 V
e todo w \u2208 \u3a3\u2217 tal que w 6= \u3bb. Suponha agora que X n+1\u21d2G\u2032 w para X \u2208 V e w \u2208 \u3a3\u2217 tal
que w 6= \u3bb, arbitra´rios. Neste caso,
X
1\u21d2G\u2032 Z1Z2 . . . Zk n\u21d2G\u2032 w = x1x2 . . . xk,
onde Zi
pi\u21d2G xi, para cada 1 \u2264 i \u2264 k, sendo pi \u2264 n. Como X \u2192 Z1Z2 . . . Zk \u2208 R\u2032, segue-
se que ha´ em R uma regra X \u2192 y onde Z1Z2 . . . Zk e´ obtida de y pela eliminac¸a\u2dco de zero
ou mais varia´veis anula´veis. Portanto, X
\u2217\u21d2G Z1Z2 . . . Zk. Se Zi e´ uma varia´vel, pela
hipo´tese de induc¸a\u2dco tem-se que Zi
\u2217\u21d2G xi. Logo, Z1Z2 . . . Zk \u2217\u21d2G x1x2 . . . xk. Concluindo:
X
\u2217\u21d2G Z1Z2 . . . Zk \u2217\u21d2G w = x1x2 . . . xk.
Na Figura 3.22 esta´ apresentado um algoritmo para eliminac¸a\u2dco de regras \u3bb abstra´\u131do
do me´todo apresentado no Teorema 19. Tal algoritmo utiliza o algoritmo definido na
Figura 3.21, para determinar o conjunto das varia´veis anula´veis. Segue um exemplo.
Exemplo 111 Seja a grama´tica G = ({P,A,B,C}, {a, b, c}, R, P ), onde R conte´m as
regras:
171
Entrada: uma GLC G = (V,\u3a3, R, P );
Sa´\u131da: uma GLC G\u2032 equivalente a G, sem regras \u3bb, exceto P \u2192 \u3bb.
A \u2190 varia´veis anula´veis de G;
R\u2032 \u2190 \u2205;
para cada regra X \u2192 w \u2208 R fac¸a
para cada forma de escrever w como x1Y1x2 . . . Ynxn+1, com Y1 . . . Yn \u2208 A fac¸a
R\u2032 \u2190 R\u2032 \u222a {X \u2192 x1x2 . . . xn+1}
fimpara;
fimpara;
retorne G\u2032 = (V,\u3a3, R\u2032 \u2212 {X \u2192 \u3bb | X 6= P}, P ).
Figura 3.22: Algoritmo para eliminar regras \u3bb.
P \u2192 APB | C
A\u2192 AaaA | \u3bb
B \u2192 BBb | C
C \u2192 cC | \u3bb
Aplicando-se o algoritmo da Figura 3.21, obte´m-se o conjunto das varia´veis anula´veis de
G: no presente caso, e´ o conjunto de todas as varia´veis de G. Em seguida, faz-se como
mostrado no algoritmo da Figura 3.22, obtendo-se as seguintes regras:
P \u2192 APB | AP | AB | PB | A | B | C | \u3bb
A\u2192 AaaA | aaA | Aaa | aa
B \u2192 BBb | Bb | b | C
C \u2192 cC | c
A regra P \u2192 P , obtida a partir da regra P \u2192 APB, foi descartada por motivos o´bvios.
Antes da apresentac¸a\u2dco das formas normais ja´ citadas, resta apresentar umme´todo para
eliminac¸a\u2dco de regras unita´rias. O me´todo fara´ uso do conceito de varia´veis encadeadas.
Seja uma grama´tica G = (V,\u3a3, R, P ). Diz-se que uma varia´vel Z \u2208 V e´ encadeada a uma
varia´vel X \u2208 V se Z = X ou se existe uma sequ¨e\u2c6ncia de regras X \u2192 Y1, Y1 \u2192 Y2, . . . ,
Yn \u2192 Z em R, n \u2265 0; no caso em que n = 0, tem-se apenas a regra X \u2192 Z. Ao conjunto
de todas as varia´veis encadeadas a X e´ dado o nome de enc(X). Note que X \u2208 enc(X).
O algoritmo da Figura 3.23 calcula tal conjunto.
Teorema 20 Seja uma GLC G. Existe uma GLC, equivalente a G, sem regras unita´rias.
Prova
Uma GLC equivalente a G = (V,\u3a3, R, P ) seria G\u2032 = (V,\u3a3, R\u2032, P ), onde
R\u2032 = {X \u2192 w | Y \u2208 enc(X), Y \u2192 w \u2208 R e w 6\u2208 V }.
172
Entrada: (1) uma GLC G = (V,\u3a3, R, P ), e
(2) uma varia´vel X \u2208 V .
Sa´\u131da: enc(X).
U \u2190 \u2205; N \u2190 {X};
repita
U \u2190 U \u222aN ;
N \u2190 {Y 6\u2208 U | Z \u2192 Y \u2208 R para algum Z \u2208 N}
ate´ N = \u2205
retorne U .
Figura 3.23: Algoritmo para varia´veis encadeadas.
Para provar a equivale\u2c6ncia entre G e G\u2032, sera´ mostrado que para todo X \u2208 V e todo
w \u2208 \u3a3\u2217 X \u2217\u21d2G w se, e somente se X \u2217\u21d2G\u2032 w.
(\u2192)
Sera´ mostrado, por induc¸a\u2dco sobre n, que para todo n \u2265 0, para todo X \u2208 V e todo
w \u2208 \u3a3\u2217 se X n\u21d2G w enta\u2dco X \u2217\u21d2G\u2032 w.
Para n = 0, sendo X \u2208 V , na\u2dco existe w \u2208 \u3a3\u2217 tal que X 0\u21d2G w; logo, a afirmativa
vale por vacuidade. Seja n \u2265 0 arbitra´rio, e suponha, como hipo´tese de induc¸a\u2dco, que
para todo X \u2208 V e todo w \u2208 \u3a3\u2217 se X n\u21d2G w enta\u2dco X \u2217\u21d2G\u2032 w. Sejam X \u2208 V e w \u2208 \u3a3\u2217
arbitra´rios e suponha que X
n+1\u21d2G w. Neste caso,
X \u21d2G Y1 \u21d2G Y2 . . .\u21d2G Yk n+1\u2212k\u21d2G w,
onde Y1, Y2, . . . , Yk\u22121 \u2208 V e Yk 6\u2208 V , k \u2265 1. Pela