AULA 11: AUTOMATO COM PILHA (CAPITULO 8)
===============================
  preparado utilizando a apostila do Prof. Newton Vieira e 
  o Capitulo 5 do livro "Introduction of Automata
  Theory, Languages, and Computation", J.E. Hopcroft, J.D. Ullman

- Problema do reconhecimento de um linguagem livre de contexto por um
  automato: o automato nao consegue "contar" ou "lembrar" o que foi
  previamente lido ou processado.

  Exemplo: {wcw^R | w em {a,b}*}

- Solucao: automato com pilha:
  Ideia: pilha de pratos:

   - le a, empilha prato Azul
   - le b, empilha prato Bege
   - le c, para de empilhar e comeca a desempilhar
   - le a e topo da pilha e' Azul, desempilha o prato
   - le b e topo da pilha e' Bege, desempilha o prato

   - todas as outras alternativas, erro.

  Arquitetura:






  Automato de pilha para o exemplo anterior:







DEF: um automato com pilha (PDA) (estendido -- porque e' permitido empilhar
mais de um simbolo na pilha a cada transicao) e' uma sextupla (Q, Sigma,
Gama, delta, q0, F), onde: 
 - Q e' um conjunto finito de estados
 - Sigma e' o alfabeto de entrada
 - Gama e' o alfabeto da pilha
 - delta e' a funcao de transicao definida de Q x (Sigma uniao {epsilon}) x
(Gama uniao {epsilon} para subconjuntos de Q x Gama*
 - q0 em Q e' o estado final
 - F subconjunto de Q e' o conjunto de estados finais.

Significado de delta(e,a,b) = {(e', cz)}:
  - a not= epsilon, b not= epsilon, c not= epsilon: 
    estando no estado e, se o proximo simbolo de entrada for a, e o simbolo
    no topo da pilha for b, mude para o estado e', consuma o simbolo de entrada
    a, desempilhe b e empilhe cz, onde c e' o novo topo da pilha.
  - se a = epsilon, nao e' consumido o simbolo de entrada
  - se b = epsilon, a transicao e' feita sem consultar o simbolo da pilha e
    nada e' desempilhado.
  - se cz = epsilon, entao nada e' empilhado.


Um automato de pilha pode nao parar:

Exemplo:









DEF: a configuracao instantanea de um PDA e' uma tripla ordenada [qi, w, alfa],
onde qi e' o estado atual, w pertencente a Sigma* e' a parte do string de
entrada ainda nao processado, e alfa pertence a Gama* e' a pilha.

DEF: A relacao |-M (resulta) e' definida por:
  [qi, aw, bz] |-M [qj, w, cz],  onde (qj, c) pertence a delta(qi,a,b),
onde a pertence a Sigma U {epsilon}, w pertence a Sigma*, b pertence a 
Gama U {epsilon}, e c, z pertencem a Gama*,  e delta e' a funcao de 
trasicao de M.

A funcao |- permite mostrar a evolucao das configuracoes durante o
processamento de uma palavra.  

Exemplo (usando o  PDA do exemplo anterior):
   [q0,abcba,epsilon] |- [q0,bcba,A] |- [q0,cba,BA] |-
   [q1,ba,BA] |- [q1,a, A] |- [q1, epsilon,epsilon]

|-* e' o fecho transitivo e reflexivo de |-


Exemplos de palavras aceitas e nao pelo PDA:
  aceitas: c, bcb, aacaa
  nao aceitas: ca, cc, aa

DEF: Seja M=(Q,Sigma,Gama,delta,q0,F) um PDA.  Uma palavra w e' aceita por
M se existe uma computacao [q0,w,epsilon] |-* [qi,epsilon,epsilon], onde
qi pertence a F.  A linguagem de M, denotada por L(M) e' o conjunto de
todas as palavras aceitas por M.

Exemplos de PDA:
1) {ww^r | w in {0,1}*}  introduz nao determinismo
 









2) {a^i b^j | i > j}












3) {w in {a,b}^* | #b's = 2* #a's}