AULA 12: PDA's (continuacao):
============================

PDA deterministico:  importantes porque geram reconhecedores de linguagens
------------------   eficientes. 

Def: duas transicoes delta(e,a,b) e delta(e,a',b') sao compativeis se e
somente se
  (a=a' ou a=epsilon ou a'=epsilon) e (b=b'ou b=epsilon ou b'=epsilon)


Def: PDA=(Q, Sigma, Gama, delta, q0, F) e'
deterministico se a funcao de transicao delta e' definida de
Q x (Sigma uniao {epsilon}) x (Gama uniao {epsilon}) para Q x (Gama uniao
{epsilon}, sem transicoes compativeis.

Exemplos: 
1) {a^i b^i | i >= 0}









2) {w em {0,1}* | #a's = #b's}









Versao nao deterministica para a mesma linguagem:













DEFINICOES ALTERNATIVAS DE RECONHECIMENTO DE PALAVRAS POR UM PDA:
Seja o PDA M=(Q, Sigma, Gama, delta, q0, F).

 1) por estado final
    L_f(M) = { w em Sigma* | [q0,w,epsilon] |-* [qi,epsilon,y], 
                             onde y em Gama* e qi pertence a F}

Exemplo: 
   L = {0^m 1^n | m >= n}






 2) por pilha vazia
    L_v(M) = { w em Sigma* | [q0,w,epsilon] |-* [qi, epsilon, epsilon]}

Exemplo: 
   L = {0^m 1^n | m >= n}









- Equivalencia de aceitacao por estado final e pilha vazia, so' estado final
 e so' pilha vazia:

Teorema: Seja L uma linguagem.  As seguintes afirmativas sao equivalentes:
  (a) L pode ser reconhecida por estado final e pilha vazia
  (b) L pode ser reconhecida por estado final
  (c) L uniao {epsilon} pode ser reconhecida por pilha vazia.

(a) -> (b)
  M = (Q, Sigma, Gama, delta, q0, F) um PDA que aceita a linguagem L(M) por
estado final e pilha vazia.  Definir M', tal que L_f (M') = L(M).
  M'= (Q U {q0', f'}, Sigma, Gama U {Z0}, delta', q0', {f'}), onde 
delta' = delta acrescido das seguintes transicoes:
    . delta'(q0', epsilon, epsilon) = {(q0, Z0)}
    . delta'(q, epsilon, Z0) = {(f', epsilon)} para todo q em F






(b) -> (c)
M = (Q, Sigma, Gama, delta, q0, F) um PDA que aceita a linguagem L(M) por
estado final.  Definir M', tal que L_v (M') = L_f(M).
  M'= (Q U {q0', g, h}, Sigma, Gama U {Z0}, delta', q0', emptyset), onde 
delta' = delta acrescido das seguintes transicoes: 
    . delta'(q0', epsilon, epsilon) = {(q0, Z0)}
    . delta'(q, epsilon, epsilon) = {(g, epsilon)} para todo q em F
    . delta'(g, epsilon, X) = {(g, epsilon)} para todo X em Gama
    . delta'(g, epsilon, Z0) = {(h, epsilon)}









(c) -> (a)
M = (Q, Sigma, Gama, delta, q0, F) um PDA que aceita a linguagem L_v(M) por
pilha vazia.  Definir M', tal que L(M') = L_v(M).
  M'= (Q, Sigma, Gama, delta, q0, Q), ou seja torna-se todos os estado
finais, ja' que M ja' aceita por pilha vazia.

PDA's e linguagens livres de contexto
-------------------------------------

1) linguagem livre de contexto -> PDA:

Exemplo: {a^i b^i | i > 0}

gramatica (na F.N.Greibach):
   S -> aAB | aB
   A -> aAB | aB
   B -> b

Ideia informal: cada passo da derivacao de uma palavra equivale no PDA ao
reconhecimento de um simbolo de entrada e colocar na pilha os nao terminais
que seguem o simbolo na producao.

No exemplo:  delta(q0, a, epsilon) = {[q1, AB], [q1,B]}
             delta(q1, a, A) = {[q1, AB], [q1, B]}
             delta(q1, b, B) = {[q1, epsilon]}

Geracao/aceitacao da palavra aaabbb:

  S => aAB       [q0, aaabbb] |- [q1, aabbb, AB]
    => aaABB                  |- [q1, abbb, ABB]
    => aaaBBB                 |- [q1, bbb, BBB]
    => aaabBB                 |- [q1, bb, BB]
    => aaabbB                 |- [q1, b, B]
    => aaabbb                 |- [q1, epsilon, epsilon]


Teorema:  Se L e' uma linguagem livre de contexto.  Entao existe um PDA que
aceita L. 

Prova: seja G=(V, Sigma, P, S) um gramatica livre de contexto na
F.N.Greibach.  Definir o PDA= ({q0,q1}, Sigma, V-{S}, delta, q0, {q1}), 
onde delta e' definido por:
   delta(q0, epsilon, epsilon) = {[q1, epsilon]} se S->epsilon em P
   delta(q0, a, epsilon) = {[q1, w] | S->aw em P}
   delta(q1, a, A) = {[q1,w] | A->aw em P e A pertence a V-{S}}

Prova-se por inducao no comprimento da derivacao que S=>* uw, onde u em
Sigma* e w em V*, entao  [q0,u,epsilon] |-* [q1,epsilon,w]

2) PDA -> gramatica livre de contexto:

  Passo 1: estender o PDA com as transicoes:
    se [qj,epsilon] em delta([qi,u, epsilon]) entao 
       [qj, A] em delta([qi,u,A]) para todo A em Gama
    se [qj, B] em delta(qi,u,epsilon) entao
       [qj, BA] em delta([qi,u,A]) para todo A em Gama

  Passo 2: gerar as producoes:
   a) S-><q0,epsilon,qj> para todo qj em F
   b) para todo [qj,B] em delta(qi,x,A), onde A em GamaU{epsilon}, gerar
      {<qi,A,qk> -> x<qj,B,qk> | qk em Q}
   c) para todo [qj,BA] em delta(qi,x,A), onde A em GamaU{epsilon}, gerar
      {<qi,A,qk> -> x<qj,B,qn><qn,A,qk> | qk, qn em Q}
   d) para todo qk em Q
      <qk, epsilon, qk> -> epsilon

Ideia: a) a partir do estado inicial q0 e pilha vazia, temos que chegar a
          um estado final qj, gerando uma palavra reconhecida pelo PDA
       b) nao importa qual o estado qk que desejamos atingir a partir de qi,
          mas se existe uma transicao de qi para qj, reconhecendo x e trocando
          A por B na pilha, entao a partir de qi, podemos gerar o simbolo
          x, trocar o estado para qj, desempilhar A, empilhar B, e a partir
          de qj chegar a qk.
       c) nao importa qual o estado qk que desejamos atingir a partir de qi,
          mas se existe uma transicao de qi para qj, reconhecendo x e trocando
          A por AB na pilha, entao a partir de qi, podemos gerar o simbolo
          x, trocar o estado para qj, desempilhar A, empilhar AB, ir para
          um estado arbitrario qn e a partir de  qn chegar a qk.
       d) partir de estado qk para chegar a ele mesmo, com a pilha vazia
          significa que nada mais deve ser aceito ou gerado.

Exemplo:








    Transicao                  Regra
 
                               S-><q0,epsilon,q1>                    (a)
 
delta(q0,a,epsilon)={[q0,A]}   <q0,epsilon,q0> -> a<q0,A,q0>         (b)
                               <q0,epsilon,q1> -> a<q0,A,q1>

delta(q0,a,A) = {[q0,AA]}      <q0,A,q0> -> a<q0,A,q0><q0,A,q0> |    (c)
                                            a<q0,A,q1><q1,A,q0>
                               <q0,A,q1> -> a<q0,A,q0><q0,A,q1> |
                                            a<q0,A,q1><q1,A,q1>

delta(q0,c,epsilon) = {[q1,epsilon]}                                 (b)
                               <q0,epsilon,q0> -> c<q1,epsilon,q0>
                               <q0,epsilon,q1> -> c<q1,epsilon,q1>

delta(q0,c,A) ={[q1,A]}        <q0,A,q0> -> c<q1,A,q0>               (b)
                               <q0,A,q1> -> c<q1,A,q1>

delta(q1,b,A) = {[q1,epsilon]} <q1,A,q0> -> b<q1,epsilon,q0>         (b)
                               <q1,A,q1> -> b<q1,epsilon,q1>

                               <q0,epsilon,q0> -> epsilon            (d)
                               <q1,epsilon,q1> -> epsilon


Eliminando as transicoes que nunca geram terminais:
. As unicas variaveis que geram palavras sao: 
  S, <q0,epsilon,q0>,<q1,epsilon,q1>,<q0,epsilon,q1>,<q1,A,q1>,<q0,A,q1>
. Assim, a gramatica resultante e':

  S -> <q0,epsilon,q1>                     S -> A

  <q0,epsilon,q1> -> a<q0,A,q1>            A -> aA' | c
  <q0,epsilon,q1> -> c<q1,epsilon,q1>      
  <q0,A,q1> -> a<q0,A,q1><q1,A,q1>         A' -> aA'B  | cB
  <q0,A,q1> -> c<q1,A,q1>
  <q1,A,q1> -> b<q1,epsilon,q1>            B -> b

  <q0,epsilon,q0> -> epsilon
  <q1,epsilon,q1> -> epsilon

Reconhecimento/geracao da palavra aacbb:

   [q0,aacbb,epsilon]            S =><q0,epsilon,q1>
|- [q0,acbb,A]                     =>a<q0,A,q1>
|- [q0,cbb,AA]                     =>aa<q0,A,q1><q1,A,q1>
|- [q1,bb,AA]                      =>aac<q1,A,q1><q1,A,q1>
|- [q1,b,A]                        =>aacb<q1,epsilon,q1><q1,A,q1>
                                   =>aacb<q1,A,q1>
|- [q1,epsilon,epsilon]            =>aacbb<q1,epsilon,q1>
                                   =>aacbb