Equivalência entre ACPs e GLCs

Prévia do material em texto

EQUIVALÊNCIA ENTRE ACP’S E 
GLC’S 
Marcelo Guerra 
INTRODUÇÃO 
 Linguagens definidas por ACP’s são exatamente as LLC’s 
 A demonstração usa o esquema 
 
 
 
 
 
 A meta é provar que as seguintes linguagens são equivalentes: 
1. As linguagens livres de contexto; 
2. As linguagens que são aceitas por estado final por algum 
ACP; 
3. As linguagens que são aceitas por pilha vazia por algum 
ACP. 
 
 Na aula anterior, vimos que (2) e (3) são equivalentes. 
Veremos agora que (1) e (2) são iguais. 
Gramática 
ACP por 
pilha 
vazia 
ACP por 
estado 
final 
GRAMÁTICA → ACP 
 Dada uma GLC G construiremos um ACP P que 
simula as derivações mais à esquerda de G. 
 
 Qualquer forma sentencial que não seja uma string de 
terminais pode ser escrita na forma xAα, onde: 
 
1. A é a variável mais à esquerda. 
2. x é qualquer grupo de terminais que aparecem à 
esquerda de A. 
3. α é o string de terminais e variáveis que aparece à 
direita de A. 
 Chamamos Aα o final dessa forma sentencial à esquerda. 
 Se uma forma sentencial à esquerda consiste em apenas 
terminais, seu final é ε. 
GRAMÁTICA → ACP 
 Idéia principal: o ACP construído a partir da 
gramática: 
 deve simular a seqüência de formas sentenciais à 
esquerda que a gramática utiliza para gerar um dado 
string de terminais w. 
 
 O final de cada forma sentencial xAα aparece na 
pilha, com A no topo. 
 x será representado como tendo sido consumido da 
entrada, restando qualquer parte de w que seguir seu 
prefixo. 
 Ou seja, se w=xy, então y permanecerá na entrada. 
GRAMÁTICA → ACP 
 Suponha que o ACP esteja em uma DI (q, y, Aα) 
representando a forma sentencial à esquerda xAα. 
 
 O ACP supõe o uso da produção A → β para expandir A. 
 
 O movimento do ACP é substituir A no topo da pilha 
por β. 
 
 A nova DI será (q, y, βα). 
 
 Note que existe apenas um estado, q, para esse ACP. 
 
 
GRAMÁTICA → ACP 
 (q, y, βα) pode não ser uma representação da 
próxima forma sentencial à esquerda: 
 β pode conter um prefixo de terminais, ou 
 β pode conter apenas terminais e α conter um prefixo 
de terminais. 
 
 Esses terminais precisam ser removidos para 
expor a próxima variável no topo da pilha. 
 
 Eles são comparados com os próximos símbolos da 
entrada, para ter certeza de que as suposições na 
derivação mais à esquerda do string w são corretas. 
 
 Caso contrário, essa ramificação do ACP morre. 
GRAMÁTICA → ACP 
 Se o processamento obtiver sucesso na simulação 
da derivação mais à esquerda de w. 
 
 Todos os símbolos na pilha terão sido expandidos – se 
forem variáveis. 
 
 Ou comparados com a entrada e desempilhados – se 
forem terminais. 
 
 A pilha estará então vazia e faz-se a aceitação da 
cadeia. 
CONSTRUÇÃO FORMAL 
 Seja G = (V, T, P, S) uma GLC. Construímos o ACP 
P que aceita L(G) por pilha vazia como segue: 
 
 P = ({q}, T, V ∪ T, δ, q, S), onde a função de transição é 
definida por: 
 
1. Para cada variável A, 
 δ(q, ε, A) = {(q, β) | A → β é uma produção de G} 
 
2. Para cada terminal a, δ(q, a, a) = {(q, ε)} 
 
EXEMPLO 
 Converter a gramática 
ao lado em um ACP 
1. E  I 
2. E  E + E 
3. E  E * E 
4. E  (E) 
5. I  a 
6. I  b 
7. I  Ia 
8. I  Ib 
9. I  I0 
10. I  I1 
 
EXEMPLO 
 O conjunto de terminais é T = {0,1,a,b,+,*,(,)} que junto com 
as variáveis {E, I} formam o alfabeto da pilha. 
 
 A função de transição é: 
 
a) δ(q, ε, I) = {(q, a), (q, b), (q, Ia), (q, Ib), (q, I0), (q, I1)} 
 
b) δ(q, ε, E) = {(q, I), (q, E + E), (q, E * E), (q, (E))} 
 
c) δ(q, a, a) = {(q, ε)}, δ(q, b, b) = {(q, ε)}, δ(q, +, +) = {(q, ε)},... 
 
 (a) e (b) vêm da regra(1), as transições em (c), da regra (2), 
para qualquer outro caso, δ é vazia. 
 
 
CONVERSÃO 
DE ACP’S PARA GRAMÁTICAS 
DE ACP’S PARA GRAMÁTICAS 
 Completamos as provas de equivalência mostrando 
que para todo ACP P podemos encontrar uma 
gramática G cuja linguagem é a mesma que P aceita 
por pilha vazia. 
 
 A construção da gramática equivalente utiliza 
variáveis, e cada uma delas representa um evento, 
que consiste: 
 
1. Na extração líquida de algum símbolo X da pilha. 
2. Em uma mudança de estado, de algum p no início para q, 
quando X finalmente é substituído por ε na pilha. 
 
 Representamos uma variável desse tipo pelo símbolo 
composto [pXq]. 
DE ACP’S PARA GRAMÁTICAS 
 Mudança líquida de estado: 
 O ACP começa no estado p0, com Y1 no topo. 
 Após todos os movimentos que resultarem na extração líquida de Y1, o ACP 
entra no estado p1. 
 Então, ele prossegue até a extração líquida de Y2, enquanto lê o string de 
entrada x2 e vai para p2. 
 A computação prossegue até cada um dos símbolos na pilha ser removido. 
TEOREMA 6.14 
 Seja P = (Q, Σ, Γ, d, q0, z0) um ACP. Então existe uma 
GLC G, tal que L(G) = N(P). 
 
 Prova: construiremos G = (V, Σ, R, S), onde o conjunto de 
variáveis consiste: 
 
1. No símbolo especial S, que é o símbolo de início. 
 
2. Em todos os símbolos da forma [pXq], onde p e q são 
estados e X é um símbolo da pilha. 
 
 As produções são 
a) Para todos os estados p, G tem a produção S → [q0Z0p] 
 Deve gerar todos os strings w que fazem o ACP extrair Z0 
enquanto passa de q0 para p. 
 Ou seja, (q0, w, Z0) ⊢* (p, ε, ε). 
b) Seja d(q, a, X) contendo o par (r, Y1Y2...Yk), onde: 
1) a é um símbolo em Σ ou a = ε. 
2) k pode ser qualquer número, inclusive 0, e nesse caso o 
par é (r, ε). 
 Então, para todas as listas de estados r1, r2, ..., rk, G tem a 
produção 
 [qXrk] → a[rY1r1][r1Y2r2]...[rk-1Ykrk] 
 
 Essa produção diz que um modo de extrair X e ir do 
estado q para rk é ler a, depois usar alguma entrada 
para extrair Y1 da pilha enquanto se passa de r para 
r1, e então ler mais alguma entrada que extrai Y2 da 
pilha e vai do estado r1 a r2 e assim por diante. 
EXEMPLO 
 Vamos converter o ACP PN = ({q}, {i, e}, {Z}, dN, q, Z) 
que aceita todos os strings que violam, pela 
primeira vez, a regra de que todo else deve 
corresponder a algum if precedente. 
 
 Construção particularmente simples. Só existem duas 
variáveis na gramática G: 
 
1. S,o símbolo de início. 
 
2. [qZq], a única tripla que pode ser montada a partir dos 
estados e símbolos de pilha de PN. 
q 
e,Z/ε 
i, Z/ZZ 
EXEMPLO 
 As produções são: 
a) A única produção para S é S → [qZq] 
 Porém, se existissem n estados do ACP, então existiriam 
n produções desse tipo, pois o último estado poderia ser 
qualquer dos n estados. 
b) Do fato de que dN(q, i, Z) contém (q, ZZ), obtemos a 
produção [qZq] → i[qZq][qZq]. 
a) Se existissem n estados, essa única regra produziria n2 
produções. 
b) Exemplo: se p e r fossem dois estados quaisquer do ACP, 
então a produção [qZp] → i[qZr][rZp] seria gerada. 
c) Do fato de que dN(q, e, Z) contém (q, e), temos a produção: 
 [qZq] → e. 
q 
e,Z/ε 
i, Z/ZZ 
EXEMPLO 
 Por conveniência, podemos substituir a tripla [qZq] 
por um símbolo mais simples, por exemplo, A. 
 Assim, a gramática que obtivemos pode ser reescrita 
como: 
 S → [qZq] 
 [qZq] → i[qZq][qZq] 
 [qZq] → e 
 S  A 
 A  iAA | e 
q 
e,Z/ε 
i, Z/ZZ