As Linguagens de um ACP

Esta é uma pré-visualização de arquivo. Entre para ver o arquivo original

AS LINGUAGENS DE UM ACP 
Marcelo Guerra 
INTRODUÇÃO 
 Supomos que um ACP aceita sua entrada após 
consumir cada caractere e entrando em um estado de 
aceitação: 
1. Aceitação por estado final. 
 
 Uma segunda abordagem considera que os strings que 
fazem o ACP esvaziar sua pilha devem ser aceitos: 
2. Aceitação por pilha vazia. 
 
 Os dois métodos são equivalentes 
 Uma linguagem L é aceita por um ACP usando (1) se e 
somente se, ela é aceita por um ACP que usa (2) e vice-versa. 
 A conversão de um ACP que aceita L por estado final em 
outro ACP que aceita L por pilha vazia é possível (vice-
versa). 
ACEITAÇÃO POR ESTADO FINAL 
 Seja P = (Q, , , , q0, Z0, F) um ACP. A 
Linguagem aceita por P por estado final é: 
 { w | (q0, w, Z0) ⊢* (q, , )} 
 onde q  F e  é qualquer string em . 
 
 A partir da descrição instantânea inicial, com w 
na entrada, P consome w e entra em um estado de 
aceitação. 
 
 O conteúdo da pilha nesse instante é irrelevante. 
EXEMPLO 
 O ACP 
 
 
 
 
 
 Aceita a linguagem wwR sobre {0,1} 
 
 A prova é uma declaração se e somente se: 
 O ACP aceita o string x por estado final se e somente se 
x tem a forma wwR 
q0 q1 q2 
 
0, Z0/0Z0 
1, Z0/1Z0 
0, 0/00 
0, 1/01 
1, 0/10 
1, 1 /11 
, Z0/Z0 
 , 0/0 
, 1/1 
 
0, 0/  
1, 1/  
 
, Z0/Z0 
 
EXEMPLO 
 (Se) temos apenas que demonstrar a computação 
de aceitação de P. 
 Se x = wwR observamos que: 
 (q0, ww
R, Z0) ⊦
* (q0, w
R, wRZ0) ⊦ (q1, w
R, wRZ0) ⊦
* 
 (q1, ε, Z0) ⊦
* (q2, ε, Z0). 
 
 Como se vê, a única opção do ACP é de ler w e de 
empilhá-lo em ordem reversa. 
 
 Em seguida, indo espontaneamente para q1, ele 
compara o resto da entrada com a pilha e, por fim, ele 
vai espontaneamente para o estado q2. 
EXEMPLO 
 (Somente se) O único modo de ir para q2 é estar em 
q1 e a pilha conter apenas Z0. 
 
 Além disso, qualquer computação de aceitação de P 
começará no estado q0, fará uma transição para q1 e 
nunca retornará a q0. 
 
 Assim, é suficiente encontrar as condições em x tais 
que (q0, x, Z0) ⊦
* (q1, ε, Z0). 
 
 Podemos demonstrar por indução sobre |x| que: 
 se (q0, x, Z0) ⊦
* (q1, ε, Z0) então x tem a forma ww
R. 
EXEMPLO 
 Se (q0, x, Z0) ⊦
* (q1, ε, Z0) então x tem a forma ww
R 
 
 Base: se x = ε, então x é da forma wwR 
 
 Indução: Suponha que x = a1a2...an para n > 0. Há dois 
movimentos que P pode fazer a partir de (q0, x, ) 
1. (q0, x, ) ⊦ (q1, x, ). 
 Assim, P passa a desempilhar símbolos à medida em que x é lido, e |x|> 0. 
Portanto, se (q1, x, α) ⊦
* (q1, ε, β) então β será mais curta que α (e não poderá 
ser igual a α). 
 
2. (q0, a1a2...an, α) ⊦ (q0, a2...an, a1α), a única maneira de uma 
seqüência de movimentos terminar em (q1, ε, α) é aquela em que o 
último movimento é um pop (q1, an, a1α) ⊦ (q1, ε, α) 
 Neste caso, a1 = an e também sabemos que: 
 (q0, a2...an, a1α) ⊦
* (q1, an, a1α) 
 
Portanto, x é da forma wwR 
ACEITAÇÃO POR PILHA VAZIA 
 Para cada ACP P = (Q, , , , q0, Z0, F) definimos 
N(P) = { w | (q0, w, Z0) ⊢* (q, , ) } 
 para qualquer estado q. 
 
 Isto é, N(P) é o conjunto de entradas w que P 
pode consumir e ao mesmo tempo esvaziar a sua 
pilha. 
q0 q1 q2 
 
0, Z0/0Z0 
1, Z0/1Z0 
0, 0/00 
0, 1/01 
1, 0/10 
1, 1 /11 
, Z0/Z0 
 , 0/0 
, 1/1 
 
0, 0/  
1, 1/  
 
, Z0/ Z0 
 
EXEMPLO 
 Podemos fazer uma alteração simples no autômato anterior 
para que N(P) ≠ ∅ 
, Z0/  
 
q0 q1 q2 
 
0, Z0/0Z0 
1, Z0/1Z0 
0, 0/00 
0, 1/01 
1, 0/10 
1, 1 /11 
, Z0/Z0 
 , 0/0 
, 1/1 
 
0, 0/  
1, 1/  
 
, Z0/Z0 
 
CONVERSÃO DE ACPS 
 
PILHA VAZIA  ESTADO FINAL 
DE PILHA VAZIA AO ESTADO FINAL 
 A classe de linguagens L(P) é igual à classe N(P) 
para algum ACP P. 
 
 Essa classe também é exatamente a classe das 
LLC’s. 
 
 Teorema 6.9: Se L=N(PN) para algum ACP PN = 
(Q, , , N, q0, Z0, F) existe um ACP PF tal que 
L = L(PF). 
 
REPRESENTAÇÃO 
p0 q0 
, X0/Z0X0 PN 
, X0/  
, X0/  
, X0/  
, X0/  
pf 
REPRESENTAÇÃO 
 
 Usamos um novo símbolo X0  . 
 
 X0 é ao mesmo tempo símbolo de início de PF e marcador na parte 
inferior da pilha para PN, dizendo quando PN alcançou a pilha vazia. 
 
 Usamos um novo estado inicial p0, cuja função única é empilhar Z0, o 
símbolo de início de PN, no topo da pilha e entrar no estado q0, estado 
inicial de PN. 
 
 Então PF simula PN até a pilha de PN se esvaziar, o que PF detecta 
porque vê X0 no topo. 
 
 Finalmente, precisamos de um novo estado, pf, que é o estado final de 
PF. 
 
 Esse ACP transfere para pf sempre que nota que a pilha está vazia. 
REPRESENTAÇÃO 
 PF = (Q  {p0, pf}, ,   {X0} , F , p0, X0, {pf}) 
 
 Onde F é dado por: 
 
1. F(p0, , X0) = {(q0, Z0X0)} – em seu estado inicial, PF faz 
uma transição espontânea para o estado inicial de PN, 
empilhando seu símbolo de início Z0 sobre a pilha. 
 
2. Para todos os estados q em Q, entradas a em  ou a = , e 
símbolos da pilha Y em , F(q, a, Y) contém todos os 
pares em N(q, a, Y). 
 
3. Além da regra 2, F(q, , X0) contém (pf, ) para todo 
estado q em Q. 
EXEMPLO 
 Projetar um ACP que processa a seqüência de ifs 
e elses em um programa C. 
 
 O ACP deverá reconhecer quando uma sequência de 
ifs e elses está desbalanceada. 
 
 Quando o número de else’s excede o número de if’s, 
temos um problema em fazer a correspondência de 
cada else com seu if anterior. 
 
 Usaremos um símbolo da pilha Z para contar a 
diferença entre o número de i’s vistos até o momento 
e o número de e’s. 
EXEMPLO 
 
 
 
 
 Usando o método para construir um ACP que 
aceite a mesma linguagem por estado final, 
obtemos 
q 
e,Z/ε 
i, Z/ZZ 
q 
e,Z/ε 
i, Z/ZZ 
p q 
ε, X0/ ε ε, X0/ZX0 r 
CONVERSÃO DE ACPS 
 
 ESTADO FINAL  PILHA VAZIA 
DO ESTADO FINAL PARA A PILHA VAZIA 
 Tomamos um ACP PF que aceite uma linguagem L pelo 
estado final e construímos um ACP PN que aceita L por 
pilha vazia. 
 
 A partir de cada estado de aceitação de PF, adicione uma -
transição para um novo estado p. 
 
 Quando no estado p, PN extrai sua pilha sem consumir da 
entrada. 
 
 Sempre que PF entrar em um estado de aceitação após 
consumir a entrada w, PN esvaziará sua pilha após consumir 
w. 
 
 Para evitar que PF esvazie a pilha acidentalmente, PN 
também deve usar um marcador X0 na parte inferior da sua 
pilha, e um novo estado inicial, p0 cujo papel é de empilhá-lo. 
REPRESENTAÇÃO 
 A única maneira de Pn esvaziar sua pilha é entrando no 
estado p, pois X0 está na parte inferior da pilha e X0 não é 
um símbolo em que Pf tenha quaisquer movimentos. 
p0 q0 
p 
, X0/Z0X0 PF 
, qualquer/  
, qualquer/  
, qualquer/  
REPRESENTAÇÃO 
p0 q0 
p 
, X0/Z0X0 PF 
, qualquer/  
, qualquer/  
, qualquer/  
• Como o autômato que estamos construindo é por pilha vazia, não 
podemos correr o risco de aceitar uma cadeia que esvazie a pilha 
sem que se chegue a um estado final. 
• Essa cadeia não seria aceita pelo Pf e não deveria ser aceita por 
Pn. 
• Para evitar aceitar esse tipo de cadeia colocamos X0, pois assim a 
pilha nunca será esvaziada antes de chegar um estado final, já que 
X0 não faz parte do alfabeto da pilha de Pf. 
TEOREMA 6.11 
 Seja L a L(PF) de um ACP PF = (Q, , , F, q0, Z0, F)
então 
existe um ACP PN tal que L = N(PN). 
 
 Prova: 
 A nova construção PN = (Q  {p0, p}, ,   {X0} , N , 
p0, X0) onde N é dada por: 
 
1. N(p0, , X0) = {(q0, Z0X0)} 
 Iniciamos empilhando o símbolo inicial de PF e indo para o seu 
estado inicial. 
 
2. Para todos os estados q em Q, entradas a em  ou a = , 
e símbolos da pilha Y em , N(q, a, Y) contém todos os 
pares em F(q, a, Y) . 
 PN simula PF 
TEOREMA 6.11 
3. Para todos os estados de aceitação, q em F e 
símbolos da pilha Y em  ou Y = X0, N(q, , Y) 
contém (p, ). 
 sempre que PF aceita, PN pode começar a esvaziar 
sua pilha sem ler da entrada. 
 
 
4. Para todos os símbolos da pilha Y em  ou Y = 
X0, N(p, , Y) = {(p, )}. 
 Uma vez em p, o que só ocorre quando PF aceita, PN 
extrai cada símbolo na pilha até que ela se esvazie.