Autômatos com Pilha

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

AUTÔMATOS COM PILHA 
Marcelo Guerra 
INTRODUÇÃO 
 Voltaremos nossa atenção das LR para uma 
classe maior de linguagens “Linguagens Livres 
de Contexto”. 
INTRODUÇÃO 
 Extensão do autômato finito não determinístico 
com transições vazias para as linguagens livres 
de contexto. 
 
 Trata-se de um -AFN com a inclusão de uma 
estrutura de dados do tipo pilha. 
 Pode ser aumentada e diminuída somente no topo. 
 Modo de acesso: LIFO. 
 
 Esses autômatos aceitam exatamente as LLC’s. 
 GLCs podem ser convertidas em autômatos com pilha 
e vice-versa. 
 
DEFINIÇÃO DE AUTÔMATO COM PILHA 
 O Autômato com Pilha é análogo ao Autômato 
Finito, incluindo uma pilha como memória 
auxiliar e a facilidade de não-determinismo com 
transições vazias. 
 O autômato de pilha pode “memorizar” uma 
quantidade infinita de informações. 
 O acesso é feito apenas no topo: último a entrar 
primeiro a sair. 
 Nem toda linguagem pode ser reconhecida sem o 
acesso aleatório. 
 
Os Autômatos com pilha reconhecem todas 
as LLC’s, e somente elas. 
DEFINIÇÃO DE AUTÔMATO COM PILHA 
 Assim como algumas linguagens não são regulares 
e são livres de contexto, há linguagens que não são 
livres de contexto. 
 Exemplo: L={0n1n2n|n 1} 
 
REPRESENTAÇÃO 
 Controle de estados 
finitos: 
 Lê as entradas, um 
símbolo de cada vez. 
 Além de ler a entrada, o 
autômato pode ler o 
símbolo do topo da 
pilha para decidir em 
qual estado ele deve 
entrar. 
 Alternativamente, ele 
pode realizar transições 
espontâneas, usando  
como entrada em vez de 
um símbolo de entrada. 
 
 
Controle 
de 
Estados 
Finitos 
Entrada 
Aceitar/
rejeitar 
Pilha 
TRANSIÇÕES 
 Em uma transição, o autômato: 
 
1. Consome um símbolo da entrada. Se  for usado, a 
entrada não é alterada. 
 
2. Assume um novo estado, que pode ser igual ao 
anterior. 
 
3. Substitui o símbolo no topo da pilha por qualquer 
string, que pode: 
 ser , correspondendo à operação de pop. 
 ser o mesmo símbolo anterior, o que não altera a pilha. 
 substituir o símbolo do topo por outro. 
 ser uma string: tem como efeito a possibilidade de alterar o 
símbolo do topo da pilha, e depois inserir um ou mais 
novos símbolos na pilha. 
EXEMPLO 
 Considere a linguagem Lww
r = {wwR|w está em (0 + 1)*} 
 
 A linguagem “w-w-reverso”: palíndromos de comprimento par 
sobre o alfabeto {0,1}. 
 
 Sua gramática é 
1. P   
2. P  0P0 
3. P  1P1 
 
 Podemos projetar um Autômato com Pilha para esta 
linguagem como segue: 
EXEMPLO 
1. Começamos com um estado q0 que representa o 
palpite de que ainda não vimos o meio da string: 
não vimos w, que deve ser seguida de seu 
próprio reverso, wR. 
 Enquanto estamos em q0, lemos os símbolos e os 
armazenamos na pilha. 
 
2. Em qualquer momento, podemos supor que 
lemos o fim de w (o meio da entrada), que estará 
copiada na pilha. 
 A extremidade direita de w no topo, e a esquerda na 
parte inferior da pilha. 
 Esta escolha é interpretada como uma transição 
vazia para o estado q1. 
EXEMPLO 
3. Uma vez em q1, comparamos o símbolo de 
entrada com o símbolo do topo da pilha. 
 Se eles coincidirem, consumimos a entrada, 
extraímos o símbolo do topo e prosseguimos. 
 Caso contrário, o palpite foi errado e w não é 
seguido de wR, essa ramificação da execução 
“morre”. 
 Outras ramificações não determinísticas podem 
evoluir e levar à aceitação. 
 
4. Se esvaziamos a pilha, então, de fato vimos 
alguma entrada w, seguida por wR e aceitamos 
a entrada. 
DEFINIÇÃO FORMAL 
 Um ACP (ou PDA para pushdown automata) P é 
definido por P = (Q, , , , q0, Z0, F), onde: 
 
 Q é um conjunto finito de estados. 
 (sigma) é um conjunto finito de símbolos de entrada. 
 (gama) é o alfabeto da pilha, um conjunto finito de 
símbolos. 
 q0 é o estado inicial. 
 Z0 é o símbolo de início. 
 A pilha é iniciada com este símbolo e nada mais. 
 F é o conjunto de estados de aceitação. 
 
DEFINIÇÃO FORMAL 
  é a função de transição, que toma como 
argumentos uma tripla (q, a, X), onde: 
 
1. q é um estado de Q. 
 
2. a é um símbolo de entrada em  ou a=. 
 
3. X é um símbolo da pilha em . 
 
 A saída de  é um conjunto finito de pares (p, ), 
onde p é o novo estado e  é a string a ser escrita na 
pilha em substituição a X. 
 
EXEMPLO 
 O autômato para a linguagem wwR é dado por: 
 
 P = {{q0, q1, q2}, {0, 1}, { 0, 1, Z0}, , q0 ,Z0, {q2} } 
 
 
 Onde  é definido pelas regras: 
1. (q0, 0, Z0) = {(q0, 0Z0) } e (q0, 1, Z0) = {(q0, 1Z0) } 
 (empilha deixando Z0) 
2. (q0, 0, 0) = {(q0, 00) }, (q0, 0, 1) = {(q0, 01)}, 
(q0, 1, 0) = {(q0, 10) } e (q0, 1, 1) = {(q0, 11) } 
 (empilha) 
3. (q0, , Z0) = {(q1, Z0)}, (q0, , 0) = {(q1, 0)} e (q0, , 1) = {(q1, 1)} 
 (mudar de estado sem modificar a pilha) 
4. (q1, 0, 0) = {(q1, )} e (q1, 1, 1) = {(q1, )} 
 (extração) 
5. (q1, , Z0) = {(q2, Z0)} 
 (estado final transição vazia) 
 
P = (Q, , , , q0, Z0, F) 
NOTAÇÃO GRÁFICA 
 O diagrama de transição para PDA’s é formado 
por: 
 
 Nós correspondendo aos estados. 
 
 Uma seta indicando o estado inicial, e estados com 
círculos duplos indicando estados de aceitação. 
 
 Arcos correspondem às transições de ACP. 
 Um arco identificado por a, X/ do estado q para o estado p, 
significa que (q, a, X) contém o par (p, ). 
 
 O símbolo de início da pilha não é indicado, mas 
por convenção, usaremos Z0. 
EXEMPLO 
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 
 
Estado Atual 
Entrada 
Topo da pilha 
Como a pilha vai ficar 
EXEMPLO 
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 
 
(1) 
(1) 
(2) 
(2) 
(2) 
(2) 
(3) 
(3) 
(3) 
(4) 
(4) 
(5) 
DESCRIÇÕES INSTANTÂNEAS 
 A configuração de um PDA envolve tanto seu 
estado atual quanto o conteúdo da pilha. 
 Também é útil representar como parte da 
configuração a porção restante da entrada. 
 
 Usaremos uma tripla (q, w, ) para representar a 
configuração. 
 q é o estado corrente. 
 w é o restante da entrada. 
  é o conteúdo da pilha. 
 
 O topo da pilha aparece na extremidade esquerda 
de  e a parte inferior aparece à direita. 
DESCRIÇÕES INSTANTÂNEAS 
 O processamento (ou “computação”) realizado pelo 
PDA é denotado através da “dedução” para conectar 
pares de DI’s (Descrições Instantâneas) que 
representam um ou muitos movimentos do PDA. 
 
 Seja P = (Q, , , , q0, Z0, F) um PDA. Definimos ⊦P 
ou simplesmente ⊦ como segue: 
 Suponha que (q, a, X) contém (p, ). Então, para todos 
os strings w em * e β em *: 
 (q, aw, Xβ) ⊦ (p, w, β) 
 
Consumindo a e substituindo X por  no topo da pilha, 
podemos ir do estado q para o estado p. 
DESCRIÇÕES INSTANTÂNEAS 
 Também usamos ⊦* para representar zero ou mais 
movimentos do PDA, ou seja: 
 Base: I ⊦* I para qualquer DI I 
 Indução: I ⊦* J se existe alguma DI K tal que I ⊦ K e K ⊦* J 
 
 Ou seja, I ⊦* J se existe uma seqüência de DI’s 
K1,K2,...,Kn tal que I = K1,J=Kn, e para todo 
i = 1, 2, n, ..., n-1 temos que Ki ⊦ Ki+1 
EXEMPLO 
 Considere o PDA para a linguagem w-w-reversa 
sobre a entrada 1111. 
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 
(q0, 1111, z0) 
(q0, 111, 1z0) 
 
(q1, 1111, z0) 
 
(q2, 1111, z0) 
(q0, 11, 11z0) 
 
(q1, 111, 1z0) 
 
(q1, 11, z0) 
 
(q0, 1, 111z0) 
 
(q1, 11, 11z0) 
 
(q2, 11, z0) 
 
(q0, ε, 1111z0) 
 
(q1, 1, 111z0) 
 
(q1, 1, 1z0) 
 
(q1, ε, 1111z0) 
 
(q1, ε, 11z0) 
 
(q1, ε, z0) 
 
(q2, ε, z0) 
 
 Computação da cadeia de entrada 1111. 
3 
3 
3 
3 
2 
1 
2 
2 
5 
5 
1 
4 
5 
4 
5 
2 
EXEMPLO 
 Computação da cadeia de entrada 1111.