Computabilidade e Linguagens Formais
 Autómatos
de pilha
Gabriel David / Cristina Ribeiro
1
Autómatos e autómatos de pilha

Os autómatos de pilha estão para as linguagens sem contexto
como os autómatos estão para as linguagens regulares
Linguagens
regulares
Linguagens
sem contexto
1
1*0(1+0)*
E  I | E+E | E×E | (E)
I  a | b | Ia | Ib | I0 | I1
Start
1
Start
0
A
0,1
2
B
Autómatos de pilha-2
Ideia

Autómato de pilha é um -NFA com uma pilha de símbolos
–
–

Adiciona a possibilidade de memorizar uma quantidade infinita de
informação
Só tem acesso ao topo da pilha (LIFO), em vez de poder consultar
qualquer posição de memória, como os computadores genéricos
Funcionamento
–
–
–
–
A parte de controlo lê e consome os
entrada
símbolos da entrada
Transição para novo estado baseada
no estado corrente, símbolo de
entrada e símbolo no topo da pilha
Transição espontânea com 
Topo da pilha substituído por cadeia
Controlo de
estados finito
Aceita/
rejeita
pilha
Autómatos de pilha-3
Exemplo do palindroma

Lwwr = {wwR | w em (0+1)*}
–

palindromas de comprimento par
Linguagem sem contexto gerada pela gramática P   | 0P0 | 1P1
Construir um autómato de pilha
–
–
–
–
Estado inicial q0 significa que ainda não se atingiu o meio de wwR;
vai-se guardando na pilha os símbolos de w
A qualquer altura, adivinha-se que já se chegou ao meio (fim de w)
e faz-se uma transição  para q1; a pilha contém w, a começar no
fundo e a acabar no topo; o não determinismo é simulado pela
manutenção dos dois estados
Em q1 comparam-se os símbolos de entrada com o topo da pilha; se
não houver correspondência, a aposta foi errada e este ramo da
computação morre; outro poderá ter sucesso
Se a pilha se esvaziar (e a entrada acabar) descobriu-se w e wR
Autómatos de pilha-4
Definição

Autómato de pilha (PDA) P= (Q, , , , q0, Z0, F)
–
–
–
–
Q: conjunto finito de estados
: conjunto finito de símbolos de entrada
: alfabeto da pilha finito
: função de transição (q, a, X) = {(p1,1), …} finito


q é um estado, a um símbolo de entrada ou , X um símbolo da pilha
p1 é o novo estado, 1 é a cadeia de símbolos da pilha que substitui X no topo
–
–
–
–
–
–
1=  pop do topo da pilha
1= X pilha inalterada
1= YZ X substituído por Z e push do Y a seguir
q0: estado inicial
Z0: símbolo inicial, conteúdo inicial da pilha
F: conjunto de estados de aceitação ou finais
Autómatos de pilha-5
De novo o exemplo

PDA de Lwwr P = ({q0,q1,q2}, {0,1}, {0,1,Z0}, , q0, Z0, {q2})
–
–
–
–
–
–
Z0 usado para marcar o fundo da pilha e permitir no fim da leitura
de wwR passar para o estado de aceitação q2
(q0,0,Z0)= {(q0,0Z0)} e (q0,1,Z0)= {(q0,1Z0)} topo da pilha à esquerda
(q0,0,0)= {(q0,00)}, (q0,0,1)= {(q0,01)}, (q0,1,0)= {(q0,10)},
(q0,1,1)= {(q0,11)}
(q0,,Z0)= {(q1,Z0)}, (q0, ,0)= {(q1,0)}, (q0, ,1)= {(q1,1)}
(q1,0,0)= {(q1, )} e (q1,1,1)= {(q1, )}
(q1,,Z0)= {(q2,Z0)}
Autómatos de pilha-6
Diagrama de transição
0, Z0/0Z0
1, Z0/1Z0
0, 0/00
0, 1/01
1, 0/10
1, 1/11
Start



q0
0, 0/
1, 1/
, Z0/Z0
, 0/0
, 1/1
q1
, Z0/Z0
q2
Nós são estados
Start indica o estado inicial
Arcos correspondem às transições
–
–
Etiqueta a,X/α de q para p significa que (q,a,X) contém (p,α)
O arco indica a entrada e o topo da pilha antes e depois
Autómatos de pilha-7
Descrição instantânea

Computação de um PDA
–
–

Descrição instantânea (q,w,)
–
–
–

Evolui de configuração em configuração, em resposta a símbolos de
entrada (ou ) e alterando a pilha
Num DFA: toda a informação no estado; num PDA: estado + pilha
q: estado
w: entrada remanescente (em vez de só um símbolo, conveniência)
: conteúdo da pilha (topo à esquerda)
Passo de um PDA (Q, , , , q0, Z0, F)
–
–
–
Se (q,a,X) contiver (p,α), para todas as cadeias w em * e  em *
(q, aw, X) ├P (p,w,α)
Usa-se ├* para zero ou mais passos (computação)
Autómatos de pilha-8
Ainda o exemplo


Entrada w=1111
Descrição instantânea (DI) inicial: (q0, 1111, Z0)
(q0, 1111, Z0)
(q1, 1111, Z0)
(q0, 111, 1Z0)
(q1, 111, 1Z0)
(q2, 1111, Z0)
(q2, 11, Z0)
(q1, 11, Z0)
(q0, 11, 11Z0)
(q0, 1, 111Z0)
(q0, , 1111Z0)
(q1, 11, 11Z0)
(q1, 1, 111Z0)
(q1, 1, 1Z0)
(q1, , 11Z0)
(q1, , Z0)
(q2, , Z0)
(q1, , 1111Z0)
Autómatos de pilha-9
Princípios relativos a DI


Se uma sequência de DIs (computação) é legal para um PDA
P então a computação que resulta de adicionar uma qualquer
cadeia w à entrada em cada DI também é legal
Se uma computação é legal para um PDA P então a
computação que resulta de adicionar um qualquer conjunto
de símbolos abaixo da pilha em cada DI também é legal
–

Teorema 1: Se (q,x,α) ├* (p,y,) então (q,xw,α) ├* (p,yw,)
Se uma computação é legal para um PDA P e uma cauda da
entrada não é consumida, então a computação que resulta de
remover essa cauda da entrada em cada DI também é legal
–
Teorema 2: Se (q,xw,α) ├* (p,yw,) então (q,x,α) ├* (p,y,)
Autómatos de pilha-10
Comentários



Dados para os quais P nunca olha não podem afectar a sua
computação
Conceito semelhante à própria noção de linguagem sem
contexto: o que está ao lado não influencia a computação
Teorema 2 não é o inverso do 1 porque o que está na pilha
pode influenciar a computação mesmo sem ser descartado
–
Pode por exemplo ir sendo retirado da pilha um símbolo de cada
vez e no último passo repor tudo
Autómatos de pilha-11
Linguagens de um PDA

Aceitação por estado final
–
–
–
–

Exemplo:
–

(q0,wwR,Z0) ├* (q0,wR,wRZ0) ├ (q1,wR,wRZ0) ├* (q1,,Z0) ├ (q2,,Z0)
Aceitação por pilha vazia
–
–

Seja o PDA P = (Q, , , , q0, Z0, F)
Linguagem de P aceite por estado final
L(P) = {w | (q0,w,Z0) ├* (q,,α)} e q  F
Conteúdo final da pilha é irrelevante
N(P) = {w | (q0,w,Z0) ├* (q,,)}
Linguagem aceite por pilha vazia, conjunto de entradas w que P consome
esvaziando ao mesmo tempo a pilha (N(P) – pilha nula)
Mesmo exemplo: modificação para esvaziar a pilha e obter N(P)=L(P)
–
–
(q1,,Z0)= {(q2,Z0)} passa a ser (q1,,Z0)= {(q2,)}
(q0,wwR,Z0) ├* (q0,wR,wRZ0) ├ (q1,wR,wRZ0) ├* (q1,,Z0) ├ (q2,,)
Autómatos de pilha-12
Da pilha vazia ao estado final

Teorema: Se L = N(PN) para um PDA PN = (Q, , , N, q0, Z0)
então existe um PDA PF tal que L = L(PF)
–
–
–
Dois métodos de aceitação de uma entrada equivalentes
Embora para um PDA P possa ser L(P)  N(P)
Partindo de PN, usa-se um novo X0   como símbolo inicial de PF e
como marcador do fundo da pilha: PF vê X0 quando pilha de PN vazia
, X0/ 
, X0/ 
Start
p
0
, X0/Z0X0
q
0
pf
PN
, X0/ 
PF = (Q{p0,pf}, , {X0}, F, p0, X0,{pf})
Autómatos de pilha-13
Do estado final à pilha vazia
, any/
, any/
Start
p
0
, X0/Z0X0
q
0
p
PF
, any/
Autómatos de pilha-14
Exemplo de conversão

Defina um PDA que processe sequências de “i” e “e”,
significando if e else, construção presente em muitas
linguagens de programação, detectando sequências inválidas
(sequências que têm mais “e’s” que “i’s” num prefixo)
–
–
–
Símbolo inicial Z; pilha com Zn significa que nº i’s - nº e’s = n-1
Aceitação por pilha vazia (balanço de mais um “e” que “i”)
Conversão para aceitação por estado final
e, Z/ 
i, Z/ZZ
Start
q
pilha vazia
e, Z/ 
i, Z/ZZ
Start
p
, X0/ZX0
q
, X0/
r
Estado final
Autómatos de pilha-15
Equivalência entre PDAs e CFGs


Prova-se que as linguagens sem contexto, definidas por
CFG, são as linguagens aceites por pilha vazia por um PDA
e portanto também as aceites por estado final por um PDA
Ideia: dada uma CFG G construir um PDA que simula as
derivações mais à esquerda de G
–
–
–
–
–
Qualquer forma frásica esquerda não terminal pode ser escrita como
xAα, onde A é a variável mais à esquerda. Aα é a cauda.
CFG G = (V,T,Q,S)
PDA que aceita L(G) por pilha vazia: P = ({q}, T,VT,,q,S)
Para cada variável A: (q,,A)={(q,) | A   é produção em G}
Para cada terminal a: (q,a,a)={(q,)}
Autómatos de pilha-16
De CFG para PDA
E  I | E+E | E×E | (E)
I  a | b | Ia | Ib | I0 | I1

Dada a CFG

Obter um PDA de aceitação por pilha vazia que aceite a mesma
linguagem.
– PN = ({q}, {a,b,0,1,(,),+,×}, {a,b,0,1,(,),+,×,E,I}, , q, E)
–
(q,,I) = {(q,a), (q,b), (q,Ia), (q,Ib), (q,I0), (q,I1)}
–
(q,,E) = {(q,I), (q,E+E), (q,E×E), (q,(E))}
(q,a,a) = {(q,)}; (q,b,b)={(q,)}, (q,0,0) = {(q,)}; (q,1,1) = {(q,)};
(q,(,() = {(q,)}; (q,),)) = {(q,)}; (q,+,+) = {(q,)}; (q,×,×) = {(q,)}
–

Só um estado; processamento das variáveis espontâneo; só os terminais
consomem entrada
Autómatos de pilha-17
Exercício

Usando a CFG e o PDA para a linguagem das expressões
–
–

a)
–
–

a) obtenha uma derivação mais à esquerda de a(a+b00)
b) obtenha o traço da respectiva computação no PDA, isto é, a sequência
de Descrições Instantâneas
E  E×E  I×E  a×E  a×(E)  a×(E+E)  a×(I+E) 
a×(a+E)  a×(a+I)  a×(a+I0)  a×(a+I00)  a×(a+b00)
b)
–
–
–
–
–
–
(q, a(a+b00), E) ├ (q, a(a+b00), EE) ├ (q, a(a+b00), IE) ├
(q, a(a+b00), aE) ├ (q, (a+b00), E) ├ (q, (a+b00), E) ├
(q, (a+b00), (E)) ├ (q, a+b00), E)) ├ (q, a+b00), E+E)) ├
(q, a+b00), I+E)) ├ (q, a+b00), a+E)) ├ (q, +b00), +E)) ├
(q, b00), E)) ├ (q, b00), I)) ├ (q, b00), I0)) ├ (q, b00), I00)) ├
(q, b00), b00)) ├ (q, 00), 00)) ├ (q, 0), 0)) ├ (q,),)) ├ (q, , )
Autómatos de pilha-18
De PDA para CFG


Ideia: reconhecer que o evento fundamental num
processamento num PDA é o pop final de um símbolo da
pilha enquanto se consome entrada
Acrescentar variáveis na linguagem para
–
–

Cada eliminação definitiva de um símbolo X da pilha
Cada mudança de estado de p para q ao eliminar X, representada
por um símbolo composto [pXq]
Regra: do PDA P= (Q, , , N, q0, Z0) construir CFG G=
(V, , R, S)
–
Variáveis V: contém S e os símbolos [pXq]
Autómatos de pilha-19
De PDA para CFG (cont)

Produções R:
–
Para todos os estados p, G contém S  [q0Z0p]


–
O símbolo [q0Z0p] gera todas as cadeias w que extraem Z0 da pilha
enquanto vão do estado q0 para o estado p, (q0,w,Z0) ├* (p,,)
Então S gera todas as cadeias w que esvaziam a pilha
Se (q,a,X) contém o par (r,Y1Y2…Yk), k0, a   ou a= então para
todas as listas de estados r1,r2,…,rk, G contém
[qXrk]  a[rY1r1][r1Y2r2]…[rk-1Ykrk]

Uma forma de extrair X e ir de q a rk é ler a (pode ser ) e usar alguma
entrada para extrair Y1 ao ir de r para r1, etc.
Autómatos de pilha-20
Exemplo

Converter o PDA PN=({q},{i,e},{Z},N,q,Z) numa gramática
–

aceita as cadeias que violam pela 1ª vez a regra de que um “e” deve
corresponder a um “i” precedente
Solução:
–
–
–
só um estado q e só um símbolo de pilha Z
Duas variáveis: S, símbolo inicial; [qZq], único símbolo a partir dos
estados e símbolos de PN
Produções:




S  [qZq] (se houvesse mais estados p e r teríamos S[qZp] e S[qZr])
De N(q,i,Z)={(q,ZZ)} obter [qZq]i[qZq] [qZq] (se houvesse mais
estados p e r teríamos [qZp]i[qZr] [rZp])
De N(q,e,Z)={(q,)} obter [qZq]e (Z é substituído por nada)
Chamando A a [qZq] fica SA e A  iAA | e
Autómatos de pilha-21
Propriedades das CFL


Simplificação das CFGs  forma normal de Chomsky
Eliminação de símbolos inúteis
–
–
Símbolo útil: S * αX * w, w  T*
Símbolo gerador: X * w

–
–
–

Qualquer terminal é gerador, dele próprio!
Símbolo atingível: S * αX
Útil = gerador + atingível
Eliminar primeiro os não geradores e depois os não atingíveis
Exemplo
–
–
S  AB | a
Ab
S  a [B não é gerador]
Ab
Sa
[A não é atingível]
Autómatos de pilha-22
Eliminação de símbolos inúteis

Algoritmo: descobrir os símbolos geradores
–
–

os terminais são geradores
A  α e α só tem geradores; então A é gerador
Algoritmo: descobrir os símbolos atingíveis
–
–
S é atingível
A é atingível, Aα; então todos os símbolos em α são atingíveis
Autómatos de pilha-23
Eliminação de produções-



Variável anulável: A * 
Transformação: B  CAD passa a B  CD | CAD e
impede-se que A produza 
Algoritmo: descobrir as variáveis anuláveis
–

A  C1 C2 … Ck, todos os Ci são anuláveis; então A é anulável
Se uma linguagem L tem uma CFG então L-{} tem uma
CFG sem produções-
–
–
–
–
Determinar todos os símbolos anuláveis
Para cada A  X1 X2 … Xk se m Xi’s são anuláveis substituir por
2m produções com todas as combinações de presenças de Xi.
Excepção: se m=k, não se inclui o caso de todos os Xi ausentes
Produções A   são eliminadas
Autómatos de pilha-24
Exemplo

Gramática
–
–
–




S  AB
A  aAA | 
B  bBB | 
A e B são anuláveis, logo S também
S  AB | A | B
A  aAA | aA | aA | a
B  bBB | bB | b
Autómatos de pilha-25
Eliminação de produções unitárias

Produção unitária: A  B, em que A e B são variáveis
–
–

Eliminam-se por expansão
–
–
–
–

Podem ser úteis na eliminação de ambiguidade (ex: linguagem das
expressões)
Não são imprescindíveis; introduzem passos extra nas derivações
I  a | b | Ia | Ib | I0 | I1
F  I | (E)
TF|T×F
ET|E+T
De E  T passar a E  F | T × F a E  I | (E) | T × F e
finalmente E  a | b | Ia | Ib | I0 | I1 | (E) | T × F
–
Problema no caso de ciclos
Autómatos de pilha-26
Eliminação de produções unitárias

Algoritmo: descobrir todos os pares unitários, deriváveis
apenas com produções unitárias
–
–


(A, A) é um par unitário
(A, B) é um par unitário e B  C, C variável; então (A, C) é
unitário
Exemplo: (E, E), (T, T), (F, F), (E, T), (E, F), (E, I), (T, F),
(T, I), (F, I)
Eliminação: substituir as produções existentes de forma a
que para cada par unitário (A, B) se incluam todas as
produções da forma A  α em que B  α é uma produção
não unitária (incluir A=B)
Autómatos de pilha-27
Gramática sem produções unitárias
I  a | b | Ia | Ib | I0 | I1
F  I | (E)
TF|T×F
ET|E+T
Par
Produções
(E, E)
EE+T
(E, T)
ET×F
(E, F)
E  (E)
(E, I)
E  a | b | Ia | Ib | I0 | I1
(T, T)
TT×F
(T, F)
T  (E)
(T, I)
T  a | b | Ia | Ib | I0 | I1
(F, F)
F  (E)
(F, I)
F  a | b | Ia | Ib | I0 | I1
(I, I)
I  a | b | Ia | Ib | I0 | I1
Autómatos de pilha-28
Sequência de simplificação

Se G é uma CFG que gera uma linguagem com pelo menos
uma cadeia diferente de , existe uma CFG G1 que não tem
produções-, produções unitárias ou símbolos inúteis e
L(G1) O= L(G) – {}
–
–
–
Eliminar produções-
Eliminar produções unitárias
Eliminar símbolos inúteis
Autómatos de pilha-29
Forma normal de Chomsky (CNF)

Todas as CFL sem  têm uma gramática na forma normal de
Chomsky: sem símbolos inúteis e em que todas as produções
são da forma
–
–

A  BC (A, B, C variáveis) ou
A  a (A variável e a terminal)
Transformação
–
–
–
Começar com uma gramática sem produções-, produções unitárias
ou símbolos inúteis
Deixar as produções A  a
Passar todos os corpos de comprimento 2 ou mais para só variáveis

–
Variáveis novas D para os terminais d nesses corpos, substituir e D  d
Partir corpos de comprimento 3 ou mais em cascatas de produções
só com 2 variáveis A  B1B2…Bk para AB1C1, C1B2C2, …
Autómatos de pilha-30
Gramática das expressões

Variáveis para os terminais em corpos não isolados
–
–
–
–
–
–

Aa
Bb Z0 O1
P+
M× L( R)
E  EPT | TMF | LER | a | b | IA | IB | IZ | IO
T  TMF | LER | a | b | IA | IB | IZ | IO
F  LER | a | b | IA | IB | IZ | IO
I  a | b | IA | IB | IZ | IO
Substituir corpos compridos
–
–
–
–
E  EC1 | TC2 | LC3 | a | b | IA | IB | IZ | IO
T  TC2 | LC3 | a | b | IA | IB | IZ | IO
F  LC3 | a | b | IA | IB | IZ | IO
C1  PT
C2  MF
C3  ER
Autómatos de pilha-31
Lema da bombagem para CFL

Dimensão de uma árvore de análise
–
–

Considerar apenas o caso das CNF: árvores binárias em que as
folhas são terminais sem irmãos (produções Aa)
Numa gramática com árvore de análise CNF e colheita w terminal,
se o comprimento do maior caminho for n então |w|  2n-1
Seja L uma CFL. Existe uma constante n tal que, para
qualquer cadeia z em L com |z|n se pode escrever z=uvwxy
–
–
–
|vwx|  n a parte do meio não é demasiado comprida
vx  
pelo menos uma é não vazia
Para todo i  0, uviwxiy  L bombagem dupla, a começar em 0
Autómatos de pilha-32
Prova



Obter uma gramática CNF G para L
G contém m variáveis. Escolher n=2m. Cadeia z em L |z|  n.
Qualquer árvore de análise com caminho mais longo de
comprimento até m tem colheita até 2m-1=n/2.
–

z seria demasiado longa; árvore para z tem caminho m+1 ou maior
Na figura, o caminho A0…Aka é de comprimento k+1, km
–
–
Há pelo menos m+1 variáveis no caminho; logo há pelo menos uma
repetição de variáveis (de Ak-m a Ak).
Supõe-se Ai=Aj com k-m  i < j  k
Autómatos de pilha-33
Continuação da prova


A0
Se cadeia z suficientemente
longa, tem que haver repetições
de símbolos
Divide-se a árvore:
–
–
–
w é a colheita da subárvore de Aj
v e x são tais que vwx é a
colheita de Ai (como não há
produções unitárias pelo menos
um de v e x é não nulo)
u e y são as partes de z à
u
esquerda e à direita de vwx
Ai=Aj
Aj
v
Ak
a
w
z
x
y
Autómatos de pilha-34
Continuação da prova

Como Ai=Aj, pode-se
–
–

S
substituir a subárvore de Ai
pela de Aj, obtendo o caso
i=0, uwy.
substituir a subárvore de Aj
pela de Ai, obtendo o caso
i=2, uv2wx2y e repetir para
i=3, … (bombagem)
|vwx|n porque se pegou
num Ai próximo do fundo
da árvore, k-im, caminho
mais longo de Ai até m+1,
colheita até 2m=n
A
A
u v w
x
y
S
S
A
A
w
u
A
y
u v
x
y
A
v w
x
Autómatos de pilha-35
Lema da bombagem
LR (DFA)

no caso das LR: o lema da bombagem decorre de o número
de estados de um DFA ser finito
–

CFL (CFG)
para aceitar uma cadeia suficientemente comprida tem que haver
repetições de estados
No caso das CFL: decorre de o número de símbolos numa
CFG ser finito
–
para aceitar uma cadeia suficientemente comprida tem que haver
repetições (“duplas”) de símbolos
Autómatos de pilha-36
Provar que uma linguagem não é CFL

Seja L = {0k1k2k | k  1}. Mostre que não é CFL.
–
–
–
–
–
Supondo que L é uma CFL, existe uma constante n indicada pelo
lema da bombagem; tome-se z = 0n1n2n que faz parte de L
Fazendo z=uvwxy, sujeito a |vwx|  n e v, x não ambos nulos, temos
que vwx não pode conter simultaneamente 0’s e 2’s
Caso vwx não contém 2’s; então vx tem só 0’s e 1’s e tem pelo
menos um símbolo. Então, pelo lema da bombagem, uwy também
deveria pertencer à linguagem. Mas tem n 2’s e menos do que n 0’s
ou 1’s e portanto não pertence à linguagem.
Caso vwx não contém 0’s: argumento semelhante.
Obtém-se contradição em ambos os casos; portanto a hipótese é
falsa e L não é uma CFL
Autómatos de pilha-37
Problemas na prova

Seja L = {0k1k | k  1}. Mostre que não é CFL.
–
–
–
–

Supondo que L é uma CFL, existe uma constante n indicada pelo
lema da bombagem; tome-se z = 0n1n que faz parte de L
Fazendo z=uvwxy, sujeito a |vwx|  n e v, x não ambos nulos, pode
acontecer de escolher v= 0k e x=1k
Neste caso uviwxiy pertence sempre a L.
Não se obtém a contradição pretendida
Não se consegue provar que L não é CFL
–
De facto é uma CFL
Autómatos de pilha-38
Substituição

Seja  um alfabeto; para cada um dos seus símbolos a
define-se uma função (substituição) que associa uma
linguagem La ao símbolo
–
–

Exemplo:
–
–
–

Cadeias: se w= a1…an então s(w) é a linguagem de todas as cadeias
x1…xn tais que xi está em s(ai)
Linguagens: s(L) é a união de todos as s(w) tais que w  L
={0,1}, s(0)={anbn | n1}, s(1)={aa,bb}
Se w=01, s(w) = s(0)s(1) = {anbnaa | n1}  {anbn+2 | n1}
Se L=L(0*), s(L) = (s(0))* = an1bn1…ankbnk, para n1, …, nk qq
Teorema: seja L uma CFL e s() uma substituição que associa
a cada símbolo uma CFL; então s(L) é uma CFL.
Autómatos de pilha-39
Aplicação do teorema da substituição

As CFL são fechadas para:
–
–
–
–
–
–
União
Concatenação
Fecho (*) e fecho positivo (+)
Homomorfismo
Reverso
Intersecção com uma LR

–
Intersecção com uma CFL não é garantida
Homomorfismo inverso
Autómatos de pilha-40
CFL e intersecção


Seja L1 = {0n1n2i | n1, i1} e L2 = {0i1n2n | n1, i1}
L1 e L2 são CFL
–
–
–

S  AB
A  0A | 0
B  1B2 | 12
L1  L2 = {0n1n2n | n1}
–

S  AB
A  0A1 | 01
B  2B | 2
Já está provado que não é CFL
Logo as CFL não são fechadas para a intersecção
Autómatos de pilha-41
Complexidade das conversões

Conversões lineares no comprimento da representação
–
–
–

Conversão O(n3)
–

CFG para PDA
PDA de estado final para PDA de pilha vazia
PDA de pilha vazia para PDA de estado final
PDA para CFG (tamanho da CFG também O(n3))
Conversão O(n2)
–
CFG para CNF (tamanho da CNF também O(n2))
Autómatos de pilha-42
Propriedades de decisão das CFL

Teste de linguagem vazia
–
Verificar se S é gerador


Com estrutura de dados adequada, O(n)
Teste de pertença numa CFL
–
O(n3), usando programação dinâmica, preenchimento de tabela
S  AB | BC
X15
X14 X25
B  CC | b
X12 X23 X34 X45
X11 X22 X33 X44 X55
a2
a3
{S,A,C}
A  BA | a
X13 X24 X35
a1
{S,A,C}
a4
a5
C  AB | a
w=baaba
{B}
{B}
{S,A}
{B}
{S,C}
{S,A}
{B}
{A,C}
{A,C}
{B}
{A,C}
b
a
a
b
a
X12: X11X22; X24: X22X34X23X44
Autómatos de pilha-43
Problemas não decidíveis

Não há algoritmo para responder a estas perguntas
–
–
–
–
–
Uma dada CFG é ambígua?
Uma dada CFL é inerentemente ambígua?
A intersecção de duas CFL é vazia?
Duas CFL dadas são a mesma linguagem?
Uma CFL é o “universo” *, em que  é o seu alfabeto?
Autómatos de pilha-44