… NPDAs continuação
1
Empilhando Strings
Símbolo
Símbolo
String
de entrada desempilhado empilhado
a,
b
®
w
q1
q2
2
Exemplo:
q1
a, b ® cdf
q2
entrada
a
a
pilha
b
h
e
$
top
Push
c
d
f
h
e
$
string
empilhado
3
Outro exemplo de NPDA
NPDA M
L ( M )  { w : n a  nb }
a, $ ® 0$
a, 0 ® 00
a, 1 ® l
b, $ ® 1$
b, 1® 11
b, 0 ® l
q1
, $  $
q2
4
Exemplo de Execução: Instante 0
Entrada
a b
b a a b
a, $ ® 0$
a, 0 ® 00
a, 1 ® l
estado
corrente
b, $ ® 1$
b, 1® 11
b, 0 ® l
q1
, $  $
$
Pilha
q2
5
Instante 1
Entrada
a b
b a a b
a, $ ® 0$
a, 0 ® 00
a, 1 ® l
b, $ ® 1$
b, 1® 11
b, 0 ® l
q1
, $  $
0
$
Pilha
q2
6
Instante 3
Entrada
a b
b b a a
0
a, $ ® 0$
a, 0 ® 00
a, 1 ® l
b, $ ® 1$
b, 1® 11
b, 0 ® l
q1
, $  $
$
Pilha
q2
7
Instante 4
Entrada
a b
b b a a
a, $ ® 0$
a, 0 ® 00
a, 1 ® l
b, $ ® 1$
b, 1® 11
b, 0 ® l
q1
, $  $
1
$
Pilha
q2
8
Instante 5
Entrada
a b
b b a a
a, $ ® 0$
a, 0 ® 00
a, 1 ® l
b, $ ® 1$
b, 1® 11
b, 0 ® l
q1
, $  $
1
1
$
Pilha
q2
9
Instante 6
Entrada
a b
b b a a
a, $ ® 0$
a, 0 ® 00
a, 1 ® l
b, $ ® 1$
b, 1® 11
b, 0 ® l
q1
, $  $
1
1
$
Pilha
q2
10
Instante 7
Entrada
a b
b b a a
a, $ ® 0$
a, 0 ® 00
a, 1 ® l
b, $ ® 1$
b, 1® 11
b, 0 ® l
q1
, $  $
1
$
Pilha
q2
11
Instante 8
Entrada
a b
b b a a
a, $ ® 0$
a, 0 ® 00
a, 1 ® l
b, $ ® 1$
b, 1® 11
b, 0 ® l
$
Pilha
aceita
q1
, $  $
q2
12
Formalização de NPDAs
13
a,
b
®
w
q1
q2
Função de Transição :
 ( q1 , a , b )  {( q 2 , w )}
14
a, b  w
q2
q1
a, b  w
q3
Função de Transição:
 ( q1 , a , b )  {( q 2 , w ), ( q 3 , w )}
15
Definição Formal
Autômato de Pilha Não Determinista
NPDA
M = (Q, S, G, d, q0, F)
Estados
Estados
finais
Alfabeto
de entrada
Estado
inicial
Alfabeto
de pilha
Função de
Transição
16
Descrição Instantânea
(q, u , s)
Estado
corrente
Entrada
restante
Conteúdo
corrente
da pilha
17
Exemplo:
Descrição Instantânea
( q1 , bbb , aaa $)
Instante 4:
Entrada
a a a b b b
a, l ® a
b, a ® l
a
a
a
$
Pilha
l
,
l
®
l
b,
a
®
l
l
,
$
®
$
q3
q0
q2
q1
18
Exemplo:
Descrição Instantânea
( q 2 , bb , aa $)
Instante 5:
Entrada
a a a b b b
a, l ® a
b, a ® l
a
a
a
$
Pilha
l
,
l
®
l
b,
a
®
l
l
,
$
®
$
q3
q0
q2
q1
19
Escrevemos:
( q1 , bbb , aaa $)  ( q 2 , bb , aa $)
Instante 4
Instante 5
20
Uma computação:
( q 0 , aaabbb ,$)  ( q1 , aaabbb ,$) 
( q1 , aabbb , a $)  ( q1 , abbb , aa $)  ( q1 , bbb , aaa $) 
( q 2 , bb , aa $)  ( q 2 , b , a $)  ( q 2 ,  ,$)  ( q 3 ,  ,$)
a, l ® a
b, a ® l
l
,
l
®
l
b,
a
®
l
l
,
$
®
$
q3
q0
q2
q1
21
( q 0 , aaabbb ,$)  ( q1 , aaabbb ,$) 
( q1 , aabbb , a $)  ( q1 , abbb , aa $)  ( q1 , bbb , aaa $) 
( q 2 , bb , aa $)  ( q 2 , b , a $)  ( q 2 ,  ,$)  ( q 3 ,  ,$)
Por conveniência escrevemos:

( q 0 , aaabbb ,$)  ( q 3 ,  ,$)
22
Definição Formal
Linguagem de um NPDA M :
*
L(M ) = {w : (q0 , w,$) ≻ (q f , l, $)}
Estado inicial
Estado final
23
Exemplo:

( q 0 , aaabbb ,$)  ( q 3 ,  ,$)
aaabbb  L ( M )
NPDA M :
a, l ® a
b, a ® l
l
,
l
®
l
b,
a
®
l
l
,
$
®
$
q3
q0
q2
q1
24

n n
( q 0 , a b ,$)  ( q 3 ,  ,$)
n n
a b  L(M )
NPDA M :
a, l ® a
b, a ® l
l
,
l
®
l
b,
a
®
l
l
,
$
®
$
q3
q0
q2
q1
25
Portanto:
n n
L ( M )  { a b : n  0}
NPDA M :
a, l ® a
b, a ® l
l
,
l
®
l
b,
a
®
l
l
,
$
®
$
q3
q0
q2
q1
26
NPDAs Aceitam
Linguagens Livres de Contexto
27
Teorema:
Linguagens
(Gramáticas)
Livres de Contexto

Linguagens
Aceitas por
NPDAs
28
Prova - Passo 1:
Linguagens
(Gramáticas)
Livres de Contexto

Linguagens
Aceitas por
NPDAs
Converter qualquer gramática
livre de contexto G
em um NPDA M com: L ( G )  L ( M )
29
Prova - Passo 2:
Linguagens
(Gramáticas)
Livres de Contexto

Linguagens
Acceitas por
NPDAs
Converter qualquer NPDA M em
uma gramática livre de contexto G
com: L ( G )  L ( M )
30
Convertendo
Gramáticas Livres de Contexto
para
NPDAs
31
Exemplo de gramática: S  aSTb
S  b
T  Ta
T  
Qual seria o NPDA equivalente?
32
Gramática:
S  aSTb
NPDA:
S  b
T  Ta
T  
q0
 , S  aSTb
, S  b
 , T  Ta
a, a  
,T  
b, b  
,   S
q1
l, $ ® $
q2
33
O NPDA simula
derivações mais à esquerda da gramática
L(Gramática) = L(NPDA)
34
Gramática: S  aSTb
S  b
T  Ta
T  
Uma derivação mais à esquerda:
S  aSTb  abTb  abTab  abab
35
Execução do NPDA: Instante 0
Entrada
a b a b
 , S  aSTb
$
, S  b
estado
corrente
q0
Pilha
 , T  Ta
a, a  
,T  
b, b  
,   S
q1
l, $ ® $
q2
36
Instante 1
Entrada
a b a b
S
 , S  aSTb
$
, S  b
q0
Pilha
 , T  Ta
a, a  
,T  
b, b  
,   S
q1
l, $ ® $
q2
37
Instante 2
Entrada
S
T
a b a b
b
$
 , S  aSTb
, S  b
q0
Pilha
 , T  Ta
a, a  
,T  
b, b  
,   S
a
q1
l, $ ® $
q2
38
Instante 3
Entrada
S
T
a b a b
b
$
 , S  aSTb
, S  b
q0
Pilha
 , T  Ta
a, a  
,T  
b, b  
,   S
a
q1
l, $ ® $
q2
39
Instante 4
Entrada
b
a b a b
T
b
$
 , S  aSTb
, S  b
q0
Pilha
 , T  Ta
a, a  
,T  
b, b  
,   S
q1
l, $ ® $
q2
40
Instante 5
Entrada
b
a b a b
T
b
$
 , S  aSTb
, S  b
q0
Pilha
 , T  Ta
a, a  
,T  
b, b  
,   S
q1
l, $ ® $
q2
41
Instante 6
Entrada
T
a b a b
a
b
$
 , S  aSTb
, S  b
q0
Pilha
 , T  Ta
a, a  
,T  
b, b  
,   S
q1
l, $ ® $
q2
42
Instante 7
Entrada
T
a b a b
a
b
$
 , S  aSTb
, S  b
q0
Pilha
 , T  Ta
a, a  
,T  
b, b  
,   S
q1
l, $ ® $
q2
43
Instante 8
Entrada
a b a b
a
b
$
 , S  aSTb
, S  b
q0
Pilha
 , T  Ta
a, a  
,T  
b, b  
,   S
q1
l, $ ® $
q2
44
Instante 9
Entrada
a b a b
b
$
 , S  aSTb
, S  b
q0
Pilha
 , T  Ta
a, a  
,T  
b, b  
,   S
q1
l, $ ® $
q2
45
Instante 10
Entrada
a b a b
 , S  aSTb
$
, S  b
Pilha
 , T  Ta
a, a  
,T  
b, b  
aceita
q0
,   S
q1
l, $ ® $
q2
46
Em geral:
Dada qualquer gramática G
Podemos construir aum NPDA M
com
L (G )  L ( M )
47
Construindo um NPDA M a partir de G :
Para cada produção
Para cada terminal
a
A w
, A  w
q0
,   S
a, a  
q1
l, $ ® $
q2
48
Gramática G gera o string w
se e somente se
NPDA
M
aceita
w
L (G )  L ( M )
49
Portanto:
Para qualquer gramática livre de contexto
existe um NPDA
que aceita a mesma linguagem
gerada pela gramática
50
Convertendo
NPDAs
para
Gramáticas Livres de Contexto
51
Para qualquer NPDA M
vamos construir
uma gramática livre de contexto G com
L ( M )  L (G )
52
Intuição:
A gramática simula a máquina
Uma derivação na Gramática G :
S    abc  ABC     abc 
Configuração corrente no NPDA M
53
Uma derivação na Gramática G
:
terminais
variáveis
S    abc  ABC     abc 
Entrada processada
Conteúdo da pilha
no NPDA M
54
Algumas Modificações Necessárias
Primeiro, modificamos o NPDA:
• Ele tem um único estado final q f
• Ele esvazia a pilha
quando aceita a entrada
NPDA Original
Esvazia a pilha
qf
55
Segundo, modificamos as transições do NPDA:
todas as transições terão a forma
qi
a, B  
qj
ou
qi
a , B  CD
qj
B,C, D : símbolos de pilha
56
Exemplo de um NPDA na forma correta:
L ( M )  { w : n a  nb }
$ : símbolo inicial na pilha
a, $ ® 0$
a, 0 ® 00
a, 1 ® l
q0
b, $ ® 1$
b, 1® 11
b, 0 ® l
, $  
qf
57
A Contrução da Gramática
Gramática G :
símbolo na pilha
Variáveis:
( q i Bq j )
estados
Terminais:
Simbolos de entrada doNPDA58
Para cada transição
qi
a, B  
qj
Adicionamos a produção
( q i Bq j )  a
59
Para cada transição
qi
a , B  CD
qj
Adicionamos a produção
( q i Bq k )  a ( q j Cq l )( q l Dq k )
Para todos os estados
q k , ql
60
Símbolo de fundo de pilha
Variável inicial:
(qo $ q f )
Estado inicial
Estado final
61
Exemplo:
a, $ ® 0$
a, 0 ® 00
a, 1 ® l
q0
b, $ ® 1$
b, 1® 11
b, 0 ® l
, $  
qf
Produções na gramática:
( q 0 1q 0 )  a
62
Exemplo:
a, $ ® 0$
a, 0 ® 00
a, 1 ® l
q0
b, $ ® 1$
b, 1® 11
b, 0 ® l
, $  
qf
Produções na gramática:
( :q 0 $ q 0 )  b ( q 0 1q 0 )( q 0 $ q 0 ) | b ( q 0 1q f )( q f $ q 0 )
( q 0 $ q f )  b ( q 0 1q 0 )( q 0 $ q f ) | b ( q 0 1q f )( q f $ q f )
63
Exemplo:
a, $ ® 0$
a, 0 ® 00
a, 1 ® l
q0
b, $ ® 1$
b, 1® 11
b, 0 ® l
, $  
qf
Produções na gramática:
(q0 $ q f )  
64
Gramática resultante:
(q0 $q f ) : variável inicial
( q 0 $ q 0 )  b ( q 0 1q 0 )( q 0 $ q 0 ) | b ( q 0 1q f )( q f $ q 0 )
( q 0 $ q f )  b ( q 0 1q 0 )( q 0 $ q f ) | b ( q 0 1q f )( q f $ q f )
( q 0 1q 0 )  b ( q 0 1q 0 )( q 0 1q 0 ) | b ( q 0 1q f )( q f 1q 0 )
( q 0 1q f )  b ( q 0 1q 0 )( q 0 1q f ) | b ( q 0 1q f )( q f 1q f )
( q 0 $ q 0 )  a ( q 0 0 q 0 )( q 0 $ q 0 ) | a ( q 0 0 q f )( q f $ q 0 )
( q 0 $ q f )  a ( q 0 0 q 0 )( q 0 $ q f ) | a ( q 0 0 q f )( q f $ q f )
65
( q 0 0 q 0 )  a ( q 0 0 q 0 )( q 0 0 q 0 ) | a ( q 0 0 q f )( q f 0 q 0 )
( q 0 0 q f )  a ( q 0 0 q 0 )( q 0 0 q f ) | a ( q 0 0 q f )( q f 0 q f )
( q 0 1q 0 )  a
(q0 0 q0 )  b
(q0 $ q f )  
66
Derivação do string
(q0 $ q f ) 
abba
a ( q 0 0 q 0 )( q 0 $ q f ) 
ab ( q 0 $ q f ) 
abb ( q 0 1q 0 )( q 0 $ q f ) 
abba ( q 0 $ q f )  abba
67
Em geral, na Gramática:

(q0 $ q f )  w
se e somente se
w é aceito pelo NPDA
68
Explicação:
Pela construção da Gramática:

( q i Aq j )  w
se e somente se
no NPDA: indo de q i para q j
a pilha não muda abaixo de A
e A é removido da pilha
69