Capitulo 3 FTC Newton

Prévia do material em texto

Cap´ıtulo 3: Autoˆmatos de Pilha
Newton Jose´ Vieira
Departamento de Cieˆncia da Computac¸a˜o
Universidade Federal de Minas Gerais
16 de setembro de 2010
Newton Jose´ Vieira Cap´ıtulo 3: Autoˆmatos de Pilha
Suma´rio
1 Uma Introduc¸a˜o Informal
Newton Jose´ Vieira Cap´ıtulo 3: Autoˆmatos de Pilha
Suma´rio
1 Uma Introduc¸a˜o Informal
2 Autoˆmatos de Pilha Determin´ısticos
Newton Jose´ Vieira Cap´ıtulo 3: Autoˆmatos de Pilha
Suma´rio
1 Uma Introduc¸a˜o Informal
2 Autoˆmatos de Pilha Determin´ısticos
3 Autoˆmatos de Pilha Na˜o Determin´ısticos
Newton Jose´ Vieira Cap´ıtulo 3: Autoˆmatos de Pilha
Suma´rio
1 Uma Introduc¸a˜o Informal
2 Autoˆmatos de Pilha Determin´ısticos
3 Autoˆmatos de Pilha Na˜o Determin´ısticos
4 Grama´ticas Livres do Contexto
Definic¸a˜o e exemplos
Derivac¸o˜es e ambiguidade
Manipulac¸a˜o de grama´ticas e formas normais
GLCs e autoˆmatos de pilha
Newton Jose´ Vieira Cap´ıtulo 3: Autoˆmatos de Pilha
Uma Introduc¸a˜o Informal
Autoˆmatos de Pilha Determin´ısticos
Autoˆmatos de Pilha Na˜o Determin´ısticos
Grama´ticas Livres do Contexto
Linguagens na˜o regulares
Exemplo de linguagem na˜o regular muito comum:
Linguagem que conte´m expresso˜es aritme´ticas, como:
(nt1+t2)+t3) · · ·+tn+1)
em que n ≥ 1, cada ti e´ uma subexpressa˜o, e o nu´mero de (s e´
igual ao de )s.
Intuitivamente, um AF na˜o pode “lembrar” que leu n ocorreˆncias
de certo s´ımbolo, para n arbitra´rio.
Newton Jose´ Vieira Cap´ıtulo 3: Autoˆmatos de Pilha
Uma Introduc¸a˜o Informal
Autoˆmatos de Pilha Determin´ısticos
Autoˆmatos de Pilha Na˜o Determin´ısticos
Grama´ticas Livres do Contexto
Arquitetuta de um autoˆmato de pilha
a1 a2 · · · ai · · · an �
� fita de leitura apenas, unidirecional
@�
controle
+
δ
�
@
@
�
e registrador com estado atual
�
@
@
�
b1 topo da pilha
b2
...
bn
Newton Jose´ Vieira Cap´ıtulo 3: Autoˆmatos de Pilha
Uma Introduc¸a˜o Informal
Autoˆmatos de Pilha Determin´ısticos
Autoˆmatos de Pilha Na˜o Determin´ısticos
Grama´ticas Livres do Contexto
Transic¸a˜o de um AP
Sejam:
E : conjunto de estados;
Σ: alfabeto de entrada;
Γ: alfabeto de pilha;
Cada transic¸a˜o do AP e´ da forma
δ(e, a, b) = [e ′, z ]
e, e ′ ∈ E , a ∈ Σ ∪ {λ}, b ∈ Γ ∪ {λ} e z ∈ Γ∗.
Essa transic¸a˜o em um diagrama de estados:
�
�
�
�e -
a, b/z �
�
�
�e ′
Newton Jose´ Vieira Cap´ıtulo 3: Autoˆmatos de Pilha
Uma Introduc¸a˜o Informal
Autoˆmatos de Pilha Determin´ısticos
Autoˆmatos de Pilha Na˜o Determin´ısticos
Grama´ticas Livres do Contexto
Um exemplo de AP
Conjunto EA das expresso˜es aritme´ticas:
a) t ∈ EA;
b) se x , y ∈ EA, enta˜o (x) ∈ EA, x+y ∈ EA e x−y ∈ EA.
-
�
�
�
�ap
-t, λ/λ �
�
�
�
�
�
�
fpff
+, λ/λ;−, λ/λ
��
?
(, λ/X ��
?
), X/λ
Alfabetos:
Σ = {t, (, ),+,−};
Γ = {X};
Newton Jose´ Vieira Cap´ıtulo 3: Autoˆmatos de Pilha
Uma Introduc¸a˜o Informal
Autoˆmatos de Pilha Determin´ısticos
Autoˆmatos de Pilha Na˜o Determin´ısticos
Grama´ticas Livres do Contexto
Computac¸a˜o de um AP
Pilha: uma palavra de Γ∗. Pilha vazia: λ.
Configurac¸a˜o instantaˆnea: [e, y , p], sendo p a pilha.
Computac¸a˜o do AP quando a palavra de entrada e´ (t-(t+t)):
[ap, (t− (t+ t)), λ] ⊢ [ap, t− (t+ t)),X ]
⊢ [fp,−(t+ t)),X ]
⊢ [ap, (t+ t)),X ]
⊢ [ap, t+ t)),XX ]
⊢ [fp,+t)),XX ]
⊢ [ap, t)),XX ]
⊢ [fp, )),XX ]
⊢ [fp, ),X ]
⊢ [fp, λ, λ].
Newton Jose´ Vieira Cap´ıtulo 3: Autoˆmatos de Pilha
Uma Introduc¸a˜o Informal
Autoˆmatos de Pilha Determin´ısticos
Autoˆmatos de Pilha Na˜o Determin´ısticos
Grama´ticas Livres do Contexto
Outros exemplos/condic¸o˜es para reconhecimento
[ap, t), λ] ⊢ [fp, ), λ].
=⇒ o AP para sem consumir toda a palavra de entrada.
[ap, (t, λ] ⊢ [ap, t, X]
⊢ [fp, λ, X].
=⇒ o AP para em estado final com pilha na˜o vazia.
Para uma palavra ser reconhecida:
ela deve ser totalmente consumida;
a ma´quina deve terminar em um estado final;
a deve estar pilha vazia.
Newton Jose´ Vieira Cap´ıtulo 3: Autoˆmatos de Pilha
Uma Introduc¸a˜o Informal
Autoˆmatos de Pilha Determin´ısticos
Autoˆmatos de Pilha Na˜o Determin´ısticos
Grama´ticas Livres do Contexto
Um exemplo estranho
Seja o AP com Σ = {1} e com o diagrama de estados:
-
�
�
�
�
�
�
�
0
��
ff
λ, λ/X
Para toda palavra em {1}+, o AP na˜o para. Em particular:
[0, 1, λ] ⊢ [0, 1,X ] ⊢ [0, 1,XX ] . . .
Perguntas:
para λ, o AP para ou na˜o?
λ e´ reconhecida ou na˜o?
Newton Jose´ Vieira Cap´ıtulo 3: Autoˆmatos de Pilha
Uma Introduc¸a˜o Informal
Autoˆmatos de Pilha Determin´ısticos
Autoˆmatos de Pilha Na˜o Determin´ısticos
Grama´ticas Livres do Contexto
Transic¸o˜es compat´ıveis
Transic¸o˜es compat´ıveis
Seja δ : E × (Σ ∪ {λ})× (Γ ∪ {λ})→ E × Γ∗.
As transic¸o˜es δ(e, a, b) e δ(e, a′, b′) sa˜o compat´ıveis
se, e somente se
(a = a′ ou a = λ ou a′ = λ) e (b = b′ ou b = λ ou b′ = λ).
Ou ainda: δ(e, a, b) e δ(e, a′, b′) sa˜o incompat´ıveis se, e somente
se:
(a 6= a′ e a 6= λ e a′ 6= λ) ou (b 6= b′ e b 6= λ e b′ 6= λ).
Newton Jose´ Vieira Cap´ıtulo 3: Autoˆmatos de Pilha
Uma Introduc¸a˜o Informal
Autoˆmatos de Pilha Determin´ısticos
Autoˆmatos de Pilha Na˜o Determin´ısticos
Grama´ticas Livres do Contexto
O que e´ AP determin´ıstico
Autoˆmato de pilha determin´ıstico
Um autoˆmato de pilha determin´ıstico (APD) e´ uma seˆxtupla
(E ,Σ, Γ, δ, i ,F ), em que
E e´ um conjunto finito de um ou mais estados;
Σ e´ o alfabeto de entrada;
Γ e´ o alfabeto de pilha;
δ e´ uma func¸a˜o parcial de E × (Σ ∪ {λ})× (Γ ∪ {λ}) para
E × Γ∗, sem transic¸o˜es compat´ıveis;
i ⊆ E e´ o estado inicial;
F ⊆ E e´ o conjunto de estados finais.
Newton Jose´ Vieira Cap´ıtulo 3: Autoˆmatos de Pilha
Uma Introduc¸a˜o Informal
Autoˆmatos de Pilha Determin´ısticos
Autoˆmatos de Pilha Na˜o Determin´ısticos
Grama´ticas Livres do Contexto
A linguagem reconhecida por um APD
Seja um APD M = (E ,Σ, Γ, δ, i ,F ). Enta˜o:
∀e, e ′ ∈ E , a ∈ Σ ∪ {λ}, b ∈ Γ ∪ {λ}, x ∈ Γ∗:
∀y ∈ Σ∗, z ∈ Γ∗[e, ay , bz ] ⊢ [e ′, y , xz ]↔ δ(e, a, b) = [e ′, x ].
∗
⊢ e´ o fecho reflexivo e transitivo de ⊢.
Linguagem reconhecida por um APD
Seja M = (E ,Σ, Γ, δ, i ,F ). A linguagem reconhecida por M e´:
L(M) = {w ∈ Σ∗ | [i ,w , λ]
∗
⊢ [e, λ, λ] para algum e ∈ F}.
Newton Jose´ Vieira Cap´ıtulo 3: Autoˆmatos de Pilha
Uma Introduc¸a˜o Informal
Autoˆmatos de Pilha Determin´ısticos
Autoˆmatos de Pilha Na˜o Determin´ısticos
Grama´ticas Livres do Contexto
Exemplo
{anbn | n ∈ N} e´ reconhecida por ({a, b}, {a, b}, {X}, δ, a, {a, b}),
em que δ e´ dada por:
1. δ(a, a, λ) = [a, X];
2. δ(a, b, X) = [b, λ];
3. δ(b, b, X) = [b, λ].
Diagrama de estados:
-
�
�
�
�
�
�
�
a
��
?
a, λ/X
-b, X/λ
�
�
�
�
�
�
�
b
��
?
b, X/λ
Newton Jose´ Vieira Cap´ıtulo 3: Autoˆmatos de Pilha
Uma Introduc¸a˜o Informal
Autoˆmatos de Pilha Determin´ısticos
Autoˆmatos de Pilha Na˜o Determin´ısticos
Grama´ticas Livres do Contexto
Outro exemplo
APD que reconhece
{w ∈ {0, 1}∗ | o nu´mero de 0s em w e´ igual ao de 1s}:
-
�
�
�
�
�
�
�
igual
-1, λ/UF
0, λ/ZF
ff
λ, F/λ
�
�
�
�dif
��
ff 0, U/λ
0, Z/ZZ
1, U/UU
1, Z/λ
=⇒ Este APD utiliza uma te´cnica para verificar se a pilha
chegou ao fundo.
Newton Jose´ Vieira Cap´ıtulo 3: Autoˆmatos de Pilha
Uma Introduc¸a˜o Informal
Autoˆmatos de Pilha Determin´ısticos
Autoˆmatos de Pilha Na˜o Determin´ısticos
Grama´ticas Livres do Contexto
Mais um exemplo
APD que reconhece {0m1n# |m ≥ n}:
-
�
�
�
�0s
��
?
0, λ/X
-1, X/λ
�
�
�
�1s
��
?
1, X/λ
@
@
@
@@R
#, λ/λ
�
�
�
��	
#, λ/λ
�
�
�
�f
�
�
�
��6
λ, X/λ
{0m1n |m ≥ n} na˜opode ser reconhecida por APD!
Newton Jose´ Vieira Cap´ıtulo 3: Autoˆmatos de Pilha
Uma Introduc¸a˜o Informal
Autoˆmatos de Pilha Determin´ısticos
Autoˆmatos de Pilha Na˜o Determin´ısticos
Grama´ticas Livres do Contexto
Algoritmo para APD
Entrada: (1) o APD, dado por i , F e D, e
(2) a palavra de entrada, dada por prox .
Sa´ıda: sim ou na˜o.
e ← i ; empilhe(▽); ps ← prox();
enquanto D[e, a, b] e´ definido p/ a ∈ {ps, λ} e b ∈ {topo(), λ} fac¸a
seja D[e, a, b] = [e′, z];
se a 6= λ enta˜o ps ← prox() fimenta˜o;
se b 6= λ enta˜o desempilhe() fimenta˜o;
empilhe(z);
e ← e′
fimenquanto;
se ps = fs e topo() = ▽ e e ∈ F enta˜o
retorne sim
sena˜o
retorne na˜o
fimse
Esse “algoritmo” pode entrar em loop!Newton Jose´ Vieira Cap´ıtulo 3: Autoˆmatos de Pilha
Uma Introduc¸a˜o Informal
Autoˆmatos de Pilha Determin´ısticos
Autoˆmatos de Pilha Na˜o Determin´ısticos
Grama´ticas Livres do Contexto
O que e´ AP na˜o determin´ıstico
Autoˆmato de pilha na˜o determin´ıstico
Um autoˆmato de pilha na˜o determin´ıstico (APN) e´ uma seˆxtupla
(E ,Σ, Γ, δ, I ,F ), em que
E , Σ, Γ e F sa˜o como em APDs;
δ e´ uma func¸a˜o parcial de E × (Σ ∪ {λ})× (Γ ∪ {λ}) para D,
sendo D constitu´ıdo dos subconjuntos finitos de E × Γ∗;
I ⊆ E e´ o conjunto de estados iniciais.
Newton Jose´ Vieira Cap´ıtulo 3: Autoˆmatos de Pilha
Uma Introduc¸a˜o Informal
Autoˆmatos de Pilha Determin´ısticos
Autoˆmatos de Pilha Na˜o Determin´ısticos
Grama´ticas Livres do Contexto
A linguagem reconhecida por um APN
Linguagem reconhecida por um APN
Seja um APN M = (E ,Σ, Γ, δ, I ,F ). A linguagem reconhecida
por M e´:
L(M) = {w ∈ Σ∗ | [i ,w , λ]
∗
⊢ [e, λ, λ] para algum i ∈ I e e ∈ F}.
Newton Jose´ Vieira Cap´ıtulo 3: Autoˆmatos de Pilha
Uma Introduc¸a˜o Informal
Autoˆmatos de Pilha Determin´ısticos
Autoˆmatos de Pilha Na˜o Determin´ısticos
Grama´ticas Livres do Contexto
Exemplo de APN
APD que reconhece
{w ∈ {0, 1}∗ | o nu´mero de 0s em w e´ igual ao de 1s}:
-
�
�
�
�
�
�
�
��
?
0, U/λ
0, λ/Z;
��6
1, Z/λ
1, λ/U;
Newton Jose´ Vieira Cap´ıtulo 3: Autoˆmatos de Pilha
Uma Introduc¸a˜o Informal
Autoˆmatos de Pilha Determin´ısticos
Autoˆmatos de Pilha Na˜o Determin´ısticos
Grama´ticas Livres do Contexto
Exemplo na˜o trata´vel por APD
APN que reconhece a linguagem {w ∈ {0, 1}∗ |w = wR}:
-
�
�
�
�1
-
λ, λ/λ;
0, λ/λ;
1, λ/λ
�
�
�
�2
�
�
�
��
?
1, λ/1
0, λ/0;
��
?
1, 1/λ
0, 0/λ;
Em uma computac¸a˜o de sucesso para w :
se |w | for par, sera´ percorrida a transic¸a˜o de 1 para 2 sob λ;
se |w | for ı´mpar e o s´ımbolo do meio for a, sera´ percorrida a
transic¸a˜o de 1 para 2 sob a.
Newton Jose´ Vieira Cap´ıtulo 3: Autoˆmatos de Pilha
Uma Introduc¸a˜o Informal
Autoˆmatos de Pilha Determin´ısticos
Autoˆmatos de Pilha Na˜o Determin´ısticos
Grama´ticas Livres do Contexto
Reconhecimento por estado final
Reconhecimento por estado final
Seja um APN M = (E ,Σ, Γ, δ, I ,F ). A linguagem reconhecida por
M por estado final e´:
LF (M) = {w ∈ Σ
∗ | [i ,w , λ]
∗
⊢ [e, λ, y ] para i ∈ I , e ∈ F e y ∈ Γ∗}.
Exemplo: APNs para L = {0m1n |m ≥ n}:
-
�
�
�
�
�
�
�
a
��
?
0, λ/X
-1, X/λ
λ, X/λ �
�
�
�
�
�
�
b
��
?
1, X/λ
λ, X/λ
Aceitac¸a˜o por pilha vazia e estado final.
-
�
�
�
�
�
�
�
a
��
?
0, λ/X
-1, X/λ
�
�
�
�
�
�
�
b
��
?
1, X/λ
Aceitac¸a˜o por estado final
Newton Jose´ Vieira Cap´ıtulo 3: Autoˆmatos de Pilha
Uma Introduc¸a˜o Informal
Autoˆmatos de Pilha Determin´ısticos
Autoˆmatos de Pilha Na˜o Determin´ısticos
Grama´ticas Livres do Contexto
Reconhecimento por pilha vazia
Reconhecimento por pilha vazia
Seja um APN M = (E ,Σ, Γ, δ, I ). A linguagem reconhecida por M
por pilha vazia e´:
LV (M) = {w ∈ Σ
∗ | [i ,w , λ]
∗
⊢ [e, λ, λ] para algum i ∈ I e e ∈ E}.
Exemplo: APN para {0m1n |m ≤ n}, rec. por pilha vazia:
-
�
�
�
�a
��
?
0, λ/X
-1, X/λ
1, λ/λ �
�
�
�b
��
?
1, X/λ
1, λ/λ
Newton Jose´ Vieira Cap´ıtulo 3: Autoˆmatos de Pilha
Uma Introduc¸a˜o Informal
Autoˆmatos de Pilha Determin´ısticos
Autoˆmatos de Pilha Na˜o Determin´ısticos
Grama´ticas Livres do Contexto
Equivaleˆncia de me´todos de reconhecimento
Seja L uma linguagem. As seguinte afirmativas sa˜o equivalentes:
a) L pode ser reconhecida por pilha vazia e estado final.
b) L pode ser reconhecida por estado final.
c) L ∪ {λ} pode ser reconhecida por pilha vazia.
(a)→ (b):
-
�
�
�
�i ′
��
��*
HHHHj
λ, λ/F
λ, λ/F
�
�
�
�i1
...
�
�
�
�im
M
�
�
�
�f1
...
�
�
�
�fn
HHHHj
��
��*
�
�
�
�g
�
�
�
λ, F/λ
λ, F/λ
Newton Jose´ Vieira Cap´ıtulo 3: Autoˆmatos de Pilha
Uma Introduc¸a˜o Informal
Autoˆmatos de Pilha Determin´ısticos
Autoˆmatos de Pilha Na˜o Determin´ısticos
Grama´ticas Livres do Contexto
Equivaleˆncia de me´todos de reconhecimento
Seja L uma linguagem. As seguinte afirmativas sa˜o equivalentes:
a) L pode ser reconhecida por pilha vazia e estado final.
b) L pode ser reconhecida por estado final.
c) L ∪ {λ} pode ser reconhecida por pilha vazia.
(b)→ (c)
-
�
�
�
�i ′
��
��*
HHHHj
λ, λ/F
λ, λ/F
�
�
�
�i1
...
�
�
�
�im
M
�
�
�
�f1
...
�
�
�
�fn
PPPPPPq
��
��
��1
�
�
�
�g
λ, λ/λ
λ, λ/λ
��
?
λ,X/λ ∀X ∈ Γ
-λ, F/λ
�
�
�
�h
Newton Jose´ Vieira Cap´ıtulo 3: Autoˆmatos de Pilha
Uma Introduc¸a˜o Informal
Autoˆmatos de Pilha Determin´ısticos
Autoˆmatos de Pilha Na˜o Determin´ısticos
Grama´ticas Livres do Contexto
Equivaleˆncia de me´todos de reconhecimento
Seja L uma linguagem. As seguinte afirmativas sa˜o equivalentes:
a) L pode ser reconhecida por pilha vazia e estado final.
b) L pode ser reconhecida por estado final.
c) L ∪ {λ} pode ser reconhecida por pilha vazia.
(c)→ (a)
Se M = (E ,Σ, Γ, δ, I ), enta˜o M ′ = (E ,Σ, Γ, δ, I ,E ).
Newton Jose´ Vieira Cap´ıtulo 3: Autoˆmatos de Pilha
Uma Introduc¸a˜o Informal
Autoˆmatos de Pilha Determin´ısticos
Autoˆmatos de Pilha Na˜o Determin´ısticos
Grama´ticas Livres do Contexto
Definic¸a˜o e exemplos
Derivac¸o˜es e ambiguidade
Manipulac¸a˜o de grama´ticas e formas normais
GLCs e autoˆmatos de pilha
Grama´tica em notac¸a˜o BNF
〈programa〉 → 〈declarac¸o˜es〉 ; 〈lista-de-cmds〉 .
...
〈lista-de-cmds〉 → 〈comando〉 ; 〈lista-de-cmds〉 |
λ
〈comando〉 → 〈cmd-enquanto〉 |
〈cmd-se〉 |
〈cmd-atribuic¸a˜o〉 |
· · ·
Newton Jose´ Vieira Cap´ıtulo 3: Autoˆmatos de Pilha
Uma Introduc¸a˜o Informal
Autoˆmatos de Pilha Determin´ısticos
Autoˆmatos de Pilha Na˜o Determin´ısticos
Grama´ticas Livres do Contexto
Definic¸a˜o e exemplos
Derivac¸o˜es e ambiguidade
Manipulac¸a˜o de grama´ticas e formas normais
GLCs e autoˆmatos de pilha
Grama´tica em notac¸a˜o BNF (cont.)
〈cmd-enquanto〉 → enquanto 〈exp-lo´gica〉 fac¸a
〈lista-de-cmds〉 fimenquanto
〈cmd-se〉 → se 〈exp-lo´gica〉 enta˜o
〈lista-de-cmds〉 〈senaoses〉 〈senao〉 fimse
〈senaoses〉 → sena˜ose 〈exp-lo´gica〉 enta˜o
〈lista-de-cmds〉 〈senaoses〉 |
λ
〈senao〉 → sena˜o 〈lista-de-cmds〉 |
λ
〈cmd-atribuic¸a˜o〉 → 〈varia´vel〉 ← 〈expressa˜o〉
Newton Jose´ Vieira Cap´ıtulo 3: Autoˆmatos de Pilha
Uma Introduc¸a˜o Informal
Autoˆmatos de Pilha Determin´ısticos
Autoˆmatos de Pilha Na˜o Determin´ısticos
Grama´ticas Livres do Contexto
Definic¸a˜o e exemplos
Derivac¸o˜es e ambiguidade
Manipulac¸a˜o de grama´ticas e formas normais
GLCs e autoˆmatos de pilha
O que e´ grama´tica livre do contexto
Grama´tica livre do contexto
Uma grama´tica livre do contexto (GLC) e´ uma grama´tica
(V ,Σ,R ,P), em que cada regra tem a forma X → w , em que
X ∈ V e w ∈ (V ∪ Σ)∗.
Exemplo:
{0n1n | n ∈ N} e´gerada por G = ({P}, {0, 1},R ,P), em que R
consta das duas regras:
P → 0P1 |λ
Newton Jose´ Vieira Cap´ıtulo 3: Autoˆmatos de Pilha
Uma Introduc¸a˜o Informal
Autoˆmatos de Pilha Determin´ısticos
Autoˆmatos de Pilha Na˜o Determin´ısticos
Grama´ticas Livres do Contexto
Definic¸a˜o e exemplos
Derivac¸o˜es e ambiguidade
Manipulac¸a˜o de grama´ticas e formas normais
GLCs e autoˆmatos de pilha
Mais exemplos de GLCs
GLC que gera {w ∈ {0, 1}∗ |w = wR}:
G = ({P}, {0, 1},R ,P), tendo R as 5 regras:
P → 0P0 | 1P1 | 0 | 1 |λ
GLC que gera {w ∈ {0, 1}∗ |w tem um nu´mero igual de 0s e 1s}:
({P}, {0, 1},R ,P), tendo R as 3 regras:
P → 0P1P | 1P0P |λ
Newton Jose´ Vieira Cap´ıtulo 3: Autoˆmatos de Pilha
Uma Introduc¸a˜o Informal
Autoˆmatos de Pilha Determin´ısticos
Autoˆmatos de Pilha Na˜o Determin´ısticos
Grama´ticas Livres do Contexto
Definic¸a˜o e exemplos
Derivac¸o˜es e ambiguidade
Manipulac¸a˜o de grama´ticas e formas normais
GLCs e autoˆmatos de pilha
GLC para expresso˜es aritme´ticas
({E ,T ,F}, {t,+, ∗, (, )},R ,E ), em que R consta de:
E → E+T |T
T → T∗F |F
F → (E ) | t
Newton Jose´ Vieira Cap´ıtulo 3: Autoˆmatos de Pilha
Uma Introduc¸a˜o Informal
Autoˆmatos de Pilha Determin´ısticos
Autoˆmatos de Pilha Na˜o Determin´ısticos
Grama´ticas Livres do Contexto
Definic¸a˜o e exemplos
Derivac¸o˜es e ambiguidade
Manipulac¸a˜o de grama´ticas e formas normais
GLCs e autoˆmatos de pilha
O que e´ linguagem livre do contexto
Linguagem livre do contexto
Uma linguagem e´ dita ser uma linguagem livre do contexto se
existe uma grama´tica livre do contexto que a gera.
Newton Jose´ Vieira Cap´ıtulo 3: Autoˆmatos de Pilha
Uma Introduc¸a˜o Informal
Autoˆmatos de Pilha Determin´ısticos
Autoˆmatos de Pilha Na˜o Determin´ısticos
Grama´ticas Livres do Contexto
Definic¸a˜o e exemplos
Derivac¸o˜es e ambiguidade
Manipulac¸a˜o de grama´ticas e formas normais
GLCs e autoˆmatos de pilha
O conceito de a´rvore de derivac¸a˜o
A´rvore de derivac¸a˜o
Seja G = (V ,Σ,R ,P). Def. recursiva de a´rvore de derivac¸a˜o
(AD):
a) uma a´rvore com apenas o ve´rtice de ro´tulo P e´ uma AD;
b) se X ∈ V e´ ro´tulo de uma folha f de uma AD, enta˜o:
i. se X → λ ∈ R , enta˜o a a´rvore obtida acrescentando-se
mais um ve´rtice v com ro´tulo λ e uma aresta {f , v} e´
uma AD;
ii. se X → x1x2 . . . xn ∈ R , onde x1, x2, . . . , xn ∈ V ∪ Σ,
enta˜o a a´rvore obtida acrescentando-se mais n ve´rtices
v1, v2, . . . , vn com ro´tulos x1, x2, . . . , xn, nessa ordem, e
n arestas {f , v1}, {f , v2}, . . . , {f , vn}, e´ uma AD.
Newton Jose´ Vieira Cap´ıtulo 3: Autoˆmatos de Pilha
Uma Introduc¸a˜o Informal
Autoˆmatos de Pilha Determin´ısticos
Autoˆmatos de Pilha Na˜o Determin´ısticos
Grama´ticas Livres do Contexto
Definic¸a˜o e exemplos
Derivac¸o˜es e ambiguidade
Manipulac¸a˜o de grama´ticas e formas normais
GLCs e autoˆmatos de pilha
Exemplo de construc¸a˜o de uma AD para t*(t+t)
E → E+T |T
T → T∗F |F
F → (E ) | t
A derivac¸a˜o
E⇒ T (regra E → T )
leva a` AD:
�
�
�
E
�
�
�
T
Newton Jose´ Vieira Cap´ıtulo 3: Autoˆmatos de Pilha
Uma Introduc¸a˜o Informal
Autoˆmatos de Pilha Determin´ısticos
Autoˆmatos de Pilha Na˜o Determin´ısticos
Grama´ticas Livres do Contexto
Definic¸a˜o e exemplos
Derivac¸o˜es e ambiguidade
Manipulac¸a˜o de grama´ticas e formas normais
GLCs e autoˆmatos de pilha
Exemplo de construc¸a˜o de uma AD (cont.)
A derivac¸a˜o evolue para:
E⇒ T (regra E → T )
⇒ T∗F (regra T → T∗F )
e a AD correspondente para:
�
�
�
E
�
�
�
T
�
�
��
@
@
@@�
�
�
T
�
�
�
*
�
�
�
F
Newton Jose´ Vieira Cap´ıtulo 3: Autoˆmatos de Pilha
Uma Introduc¸a˜o Informal
Autoˆmatos de Pilha Determin´ısticos
Autoˆmatos de Pilha Na˜o Determin´ısticos
Grama´ticas Livres do Contexto
Definic¸a˜o e exemplos
Derivac¸o˜es e ambiguidade
Manipulac¸a˜o de grama´ticas e formas normais
GLCs e autoˆmatos de pilha
Exemplo de construc¸a˜o de uma AD (cont.)
Tem-se duas opc¸o˜es para continuar a derivac¸a˜o:
E⇒ T (regra E → T )
⇒ T∗F (regra T → T∗F )
⇒ F∗F (regra T → F )
ou enta˜o:
E⇒ T (regra E → T )
⇒ T∗F (regra T → T∗F )
⇒ T∗(E ) (regra F → (E )).
Newton Jose´ Vieira Cap´ıtulo 3: Autoˆmatos de Pilha
Uma Introduc¸a˜o Informal
Autoˆmatos de Pilha Determin´ısticos
Autoˆmatos de Pilha Na˜o Determin´ısticos
Grama´ticas Livres do Contexto
Definic¸a˜o e exemplos
Derivac¸o˜es e ambiguidade
Manipulac¸a˜o de grama´ticas e formas normais
GLCs e autoˆmatos de pilha
Exemplo de construc¸a˜o de uma AD (cont.)
As duas opc¸o˜es:
�
�
�
E
�
�
�
T
�
�
��
@
@
@@�
�
�
T
�
�
�
*
�
�
�
F
�
�
�
F
�
�
�
E
�
�
�
T
�
�
��
@
@
@@�
�
�
T
�
�
�
*
�
�
�
F
�
�
��
@
@
@@�
�
�
(
�
�
�
E
�
�
�
)
Newton Jose´ Vieira Cap´ıtulo 3: Autoˆmatos de Pilha
Uma Introduc¸a˜o Informal
Autoˆmatos de Pilha Determin´ısticos
Autoˆmatos de Pilha Na˜o Determin´ısticos
Grama´ticas Livres do Contexto
Definic¸a˜o e exemplos
Derivac¸o˜es e ambiguidade
Manipulac¸a˜o de grama´ticas e formas normais
GLCs e autoˆmatos de pilha
Exemplo de construc¸a˜o de uma AD/conclusa˜o
=⇒ Apo´s uma derivac¸a˜o de 11 passos tem-se uma AD para
t ∗ (t+ t).
Observac¸o˜es:
Nu´mero de passos da derivac¸a˜o: nu´mero de ve´rtices internos
de X .
A estrutura da AD e´ normalmente utilizada para associar
significado.
Mais de uma AD para w ⇒ mais de um significado para w .
Newton Jose´ Vieira Cap´ıtulo 3: Autoˆmatos de Pilha
Uma Introduc¸a˜o Informal
Autoˆmatos de Pilha Determin´ısticos
Autoˆmatos de Pilha Na˜o Determin´ısticos
Grama´ticas Livres do Contexto
Definic¸a˜o e exemplos
Derivac¸o˜es e ambiguidade
Manipulac¸a˜o de grama´ticas e formas normais
GLCs e autoˆmatos de pilha
Ambiguidade
Grama´tica amb´ıgua
Uma GLC e´ denominada amb´ıgua quando existe mais de uma AD
para alguma sentenc¸a que ela gera.
Exemplo:
GLC amb´ıgua para expresso˜es aritme´ticas:
E → E +E |E ∗E | (E ) | t
Newton Jose´ Vieira Cap´ıtulo 3: Autoˆmatos de Pilha
Uma Introduc¸a˜o Informal
Autoˆmatos de Pilha Determin´ısticos
Autoˆmatos de Pilha Na˜o Determin´ısticos
Grama´ticas Livres do Contexto
Definic¸a˜o e exemplos
Derivac¸o˜es e ambiguidade
Manipulac¸a˜o de grama´ticas e formas normais
GLCs e autoˆmatos de pilha
Demonstrando ambiguidade
E → E +E |E ∗E | (E ) | t
Duas ADs para t+t*t
�
�
�
E
�
�
��
@
@
@@�
�
�
E
�
�
�
+
�
�
�
E
�
�
�
t
�
�
��
@
@
@@�
�
�
E
�
�
�
*
�
�
�
E
�
�
�
t
�
�
�
t
�
�
�
E
�
�
��
@
@
@@�
�
�
E
�
�
�
*
�
�
�
E
�
�
�
t
�
�
��
@
@
@@�
�
�
E
�
�
�
+
�
�
�
E
�
�
�
t
�
�
�
t
Newton Jose´ Vieira Cap´ıtulo 3: Autoˆmatos de Pilha
Uma Introduc¸a˜o Informal
Autoˆmatos de Pilha Determin´ısticos
Autoˆmatos de Pilha Na˜o Determin´ısticos
Grama´ticas Livres do Contexto
Definic¸a˜o e exemplos
Derivac¸o˜es e ambiguidade
Manipulac¸a˜o de grama´ticas e formas normais
GLCs e autoˆmatos de pilha
Derivac¸o˜es mais a` esquerda e mais a` direita
Derivac¸a˜o mais a` esquerda
Uma derivac¸a˜o e´ dita mais a` esquerda (DME) se em cada passo e´
expandida a varia´vel mais a` esquerda.
Derivac¸a˜o mais a` direita
Uma derivac¸a˜o e´ dita mais a` direita (DMD) se em cada passo e´
expandida a varia´vel mais a` direita.
=⇒ Existe uma u´nica DME e uma u´nica DMD correspondentes a
uma AD e vice-versa.
Newton Jose´ Vieira Cap´ıtulo 3: Autoˆmatos de Pilha
Uma Introduc¸a˜o Informal
Autoˆmatos de Pilha Determin´ısticos
Autoˆmatosde Pilha Na˜o Determin´ısticos
Grama´ticas Livres do Contexto
Definic¸a˜o e exemplos
Derivac¸o˜es e ambiguidade
Manipulac¸a˜o de grama´ticas e formas normais
GLCs e autoˆmatos de pilha
Ambiguidade e DME e DMD
Como existe uma u´nica DME e uma u´nica DMD correspondentes a
uma AD e vice-versa:
uma GLC e´ amb´ıgua se, e somente se, existe mais de uma
DME para alguma sentenc¸a que ela gere;
uma GLC e´ amb´ıgua se, e somente se, existe mais de uma
DMD para alguma sentenc¸a que ela gere.
Newton Jose´ Vieira Cap´ıtulo 3: Autoˆmatos de Pilha
Uma Introduc¸a˜o Informal
Autoˆmatos de Pilha Determin´ısticos
Autoˆmatos de Pilha Na˜o Determin´ısticos
Grama´ticas Livres do Contexto
Definic¸a˜o e exemplos
Derivac¸o˜es e ambiguidade
Manipulac¸a˜o de grama´ticas e formas normais
GLCs e autoˆmatos de pilha
Linguagens inerentemente amb´ıguas
Linguagem inerentemente amb´ıgua: LLC para a qual existem
apenas grama´ticas amb´ıguas.
Exemplo:
{ambnck |m = n ou n = k}.
A detecc¸a˜o e remoc¸a˜o de ambiguidade em GLCs e´ muito
importante.
O problema de determinar se uma GLC e´ amb´ıgua e´
indecid´ıvel.
Newton Jose´ Vieira Cap´ıtulo 3: Autoˆmatos de Pilha
Uma Introduc¸a˜o Informal
Autoˆmatos de Pilha Determin´ısticos
Autoˆmatos de Pilha Na˜o Determin´ısticos
Grama´ticas Livres do Contexto
Definic¸a˜o e exemplos
Derivac¸o˜es e ambiguidade
Manipulac¸a˜o de grama´ticas e formas normais
GLCs e autoˆmatos de pilha
Varia´veis inu´teis
Varia´vel u´til
Seja uma GLC G = (V ,Σ,R ,P). Uma varia´vel X ∈ V e´ dita ser
u´til se, e somente se, existem u, v ∈ (V ∪ Σ)∗ e w ∈ Σ∗ tais que:
P
∗
⇒ uXv
∗
⇒ w .
Exemplo:
Seja a GLC:
P → AB | a
B → b
C → c
Que varia´veis sa˜o inu´teis?
Newton Jose´ Vieira Cap´ıtulo 3: Autoˆmatos de Pilha
Uma Introduc¸a˜o Informal
Autoˆmatos de Pilha Determin´ısticos
Autoˆmatos de Pilha Na˜o Determin´ısticos
Grama´ticas Livres do Contexto
Definic¸a˜o e exemplos
Derivac¸o˜es e ambiguidade
Manipulac¸a˜o de grama´ticas e formas normais
GLCs e autoˆmatos de pilha
Exemplo de varia´veis inu´teis
P → AB | a
B → b
C → c
C e´ inu´til: na˜o existem u e v tais que P
∗
⇒ uCv ;
A e´ inu´til: na˜o existe w ∈ Σ∗ tal que A
∗
⇒ w ;
B e´ inu´til: P
∗
⇒ uBv apenas para u = A e v = λ, e
na˜o existe w ∈ Σ∗ tal que AB
∗
⇒ w .
GLC equivalente sem s´ımbolos inu´teis:
P → a.
Newton Jose´ Vieira Cap´ıtulo 3: Autoˆmatos de Pilha
Uma Introduc¸a˜o Informal
Autoˆmatos de Pilha Determin´ısticos
Autoˆmatos de Pilha Na˜o Determin´ısticos
Grama´ticas Livres do Contexto
Definic¸a˜o e exemplos
Derivac¸o˜es e ambiguidade
Manipulac¸a˜o de grama´ticas e formas normais
GLCs e autoˆmatos de pilha
Eliminac¸a˜o de varia´veis inu´teis
Seja G = (V ,Σ,R ,P) tal que L(G ) 6= ∅.
Construc¸a˜o de uma GLC G ′′ equivalente a G , sem varia´veis inu´teis:
a) Obtenha G ′ = (V ′,Σ,R ′,P), em que:
V ′ = {X ∈ V |X
∗
⇒G w para algum w ∈ Σ
∗}, e
R ′ = {r ∈ R | r na˜o conte´m s´ımbolo de V − V ′}.
b) Obtenha G ′′ = (V ′′,Σ,R ′′,P), em que:
V ′′ = {X ∈ V ′ |P
∗
⇒G ′ uXv para algum u, v ∈
(V ′ ∪ Σ)∗}, e
R ′′ = {r ∈ R ′ | r na˜o conte´m s´ımbolo de V ′ − V ′′}.
Newton Jose´ Vieira Cap´ıtulo 3: Autoˆmatos de Pilha
Uma Introduc¸a˜o Informal
Autoˆmatos de Pilha Determin´ısticos
Autoˆmatos de Pilha Na˜o Determin´ısticos
Grama´ticas Livres do Contexto
Definic¸a˜o e exemplos
Derivac¸o˜es e ambiguidade
Manipulac¸a˜o de grama´ticas e formas normais
GLCs e autoˆmatos de pilha
Determinando varia´veis que produzem sentenc¸as
Algoritmo que determina {X ∈ V |X
∗
⇒ w para algum w ∈ Σ∗}:
Entrada: uma GLC G = (V ,Σ,R ,P).
Sa´ıda: I1 = {X ∈ V | X
∗
⇒ w para algum w ∈ Σ∗}.
I1 ← ∅;
repita
N ← {X 6∈ I1 | X → z ∈ R e z ∈ (I1 ∪ Σ)
∗};
I1 ← I1 ∪N
ate´ N = ∅;
retorne I1.
Newton Jose´ Vieira Cap´ıtulo 3: Autoˆmatos de Pilha
Uma Introduc¸a˜o Informal
Autoˆmatos de Pilha Determin´ısticos
Autoˆmatos de Pilha Na˜o Determin´ısticos
Grama´ticas Livres do Contexto
Definic¸a˜o e exemplos
Derivac¸o˜es e ambiguidade
Manipulac¸a˜o de grama´ticas e formas normais
GLCs e autoˆmatos de pilha
Determinando varia´veis alcanc¸a´veis a partir de P
Algoritmo que determina
{X ∈ V |P
∗
⇒ uXv para algum u, v ∈ (V ∪ Σ)∗}:
Entrada: uma GLC G = (V ,Σ,R ,P).
Sa´ıda: I2 = {X ∈ V | P
∗
⇒ uXv para algum u, v ∈ (V ∪ Σ)∗}.
I2 ← ∅; N ← {P};
repita
I2 ← I2 ∪N ;
N ← {Y 6∈ I2 | X → uYv para algum X ∈ N e u, v ∈ (V ∪ Σ)
∗}
ate´ N = ∅;
retorne I2.
Newton Jose´ Vieira Cap´ıtulo 3: Autoˆmatos de Pilha
Uma Introduc¸a˜o Informal
Autoˆmatos de Pilha Determin´ısticos
Autoˆmatos de Pilha Na˜o Determin´ısticos
Grama´ticas Livres do Contexto
Definic¸a˜o e exemplos
Derivac¸o˜es e ambiguidade
Manipulac¸a˜o de grama´ticas e formas normais
GLCs e autoˆmatos de pilha
Exemplo/eliminac¸a˜o de varia´veis inu´teis
A → ABC |AEF | BD
B → B0 | 0
C → 0C |EB
D → 1D | 1
E → BE
F → 1F1 | 1
V ′ = {B ,D,F ,A} ⇒ A → BD
B → B0 | 0
D → 1D | 1
F → 1F1 | 1
V ′′ = {A,B ,D} ⇒ A → BD
B → B0 | 0
D → 1D | 1
Newton Jose´ Vieira Cap´ıtulo 3: Autoˆmatos de Pilha
Uma Introduc¸a˜o Informal
Autoˆmatos de Pilha Determin´ısticos
Autoˆmatos de Pilha Na˜o Determin´ısticos
Grama´ticas Livres do Contexto
Definic¸a˜o e exemplos
Derivac¸o˜es e ambiguidade
Manipulac¸a˜o de grama´ticas e formas normais
GLCs e autoˆmatos de pilha
Eliminac¸a˜o de uma regra
Seja uma GLC G = (V ,Σ,R ,P). Seja X → w ∈ R , X 6= P .
Seja a GLC G ′ = (V ,Σ,R ′,P) em que R ′ e´ obtido assim:
1 para cada regra de R em que X na˜o ocorre do lado direito,
exceto X → w , coloque-a em R ′;
2 para cada regra de R da forma Y → x1Xx2X . . .Xxn+1, com
pelo menos uma ocorreˆncia de X do lado direito, com n ≥ 1 e
xi ∈ [(V − {X}) ∪ Σ]
∗, coloque em R ′ todas as regras da
forma Y → x1γ1x2γ2 . . . γnxn+1, sendo que cada γj pode ser
X ou w , com excec¸a˜o da regra X → w .
G ′ e´ equivalente a G .
Newton Jose´ Vieira Cap´ıtulo 3: Autoˆmatos de Pilha
Uma Introduc¸a˜o Informal
Autoˆmatos de Pilha Determin´ısticos
Autoˆmatos de Pilha Na˜o Determin´ısticos
Grama´ticas Livres do Contexto
Definic¸a˜o e exemplos
Derivac¸o˜es e ambiguidade
Manipulac¸a˜o de grama´ticas e formas normais
GLCs e autoˆmatos de pilha
Exemplo/eliminac¸a˜o de uma regra
GLC G :
P → ABA
A → aA | a
B → bBc |λ
GLC G ′ obtida eliminando-se a regra A→ a:
P → ABA |ABa | aBA | aBa
A → aA | aa
B → bBc |λ
Como sa˜o as derivac¸o˜es de aa em G e em G ′?
Newton Jose´ Vieira Cap´ıtulo 3: Autoˆmatos de Pilha
Uma Introduc¸a˜o Informal
Autoˆmatos de Pilha Determin´ısticos
Autoˆmatos de Pilha Na˜o Determin´ısticos
Grama´ticas Livres do Contexto
Definic¸a˜o e exemplos
Derivac¸o˜es e ambiguidade
Manipulac¸a˜o de grama´ticas e formas normais
GLCs e autoˆmatos de pilha
O conceito de varia´veis anula´veis
Varia´vel anula´vel
Uma varia´vel X e´ anula´vel em uma GLC G se, e somente se,
X
∗
⇒G λ.
Algoritmo que determina o conjunto das varia´veis anula´veis de
uma GLC:
Entrada: uma GLC G = (V ,Σ,R,P);
Sa´ıda: {X ∈ V | X
∗
⇒ λ}.
A ← ∅;
repita
N ← {Y 6∈ A | Y → z ∈ R e z ∈ A∗};
A ← A∪N
ate´ N = ∅;
retorne A.
Newton Jose´ Vieira Cap´ıtulo 3: Autoˆmatos de Pilha
Uma Introduc¸a˜o Informal
Autoˆmatos de Pilha Determin´ısticos
Autoˆmatos de Pilha Na˜o Determin´ısticos
Grama´ticas Livres do Contexto
Definic¸a˜o e exemplos
Derivac¸o˜es e ambiguidade
Manipulac¸a˜o de grama´ticas e formas normais
GLCs e autoˆmatos de pilha
Eliminac¸a˜o de regras λ
Seja G = (V ,Σ,R ,P). Seja G ′ = (V ,Σ,R ′,P) em que R ′ e´
obtido assim:
1 para cada regra de R cujo lado direito na˜o conte´m varia´vel
anula´vel, exceto regra λ, coloque-a em R ′;
2 para cada regra de R da forma Y → x1X1x2X2 . . .Xnxn+1,
sendo cada Xi uma varia´vel anula´vel, com n ≥ 1 e cada xisem varia´veis anula´veis, coloque em R ′ todas as regras da
forma Y → x1γ1x2γ2 . . . γnxn+1, em que cada γj pode ser Xj
ou λ, com excec¸a˜o de regra λ;
3 se P for anula´vel, coloque P → λ em R ′.
L(G ′) = L(G ) e sua u´nica regra λ, se houver, e´ P → λ.
Newton Jose´ Vieira Cap´ıtulo 3: Autoˆmatos de Pilha
Uma Introduc¸a˜o Informal
Autoˆmatos de Pilha Determin´ısticos
Autoˆmatos de Pilha Na˜o Determin´ısticos
Grama´ticas Livres do Contexto
Definic¸a˜o e exemplos
Derivac¸o˜es e ambiguidade
Manipulac¸a˜o de grama´ticas e formas normais
GLCs e autoˆmatos de pilha
Exemplo/eliminac¸a˜o de regras λ
Seja G :
P → APB |C
A → AaaA |λ
B → BBb |C
C → cC |λ
Varia´veis anula´veis de G : {A,C ,P ,B}. G ′:
P → APB |AP |AB |PB |A |B |C |λ
A → AaaA | aaA |Aaa | aa
B → BBb |Bb | b |C
C → cC | c
Newton Jose´ Vieira Cap´ıtulo 3: Autoˆmatos de Pilha
Uma Introduc¸a˜o Informal
Autoˆmatos de Pilha Determin´ısticos
Autoˆmatos de Pilha Na˜o Determin´ısticos
Grama´ticas Livres do Contexto
Definic¸a˜o e exemplos
Derivac¸o˜es e ambiguidade
Manipulac¸a˜o de grama´ticas e formas normais
GLCs e autoˆmatos de pilha
O conceito de varia´veis encadeadas
Varia´vel encadeada
Seja uma grama´tica G = (V ,Σ,R ,P). Diz-se que uma varia´vel
Z ∈ V e´ encadeada a uma varia´vel X ∈ V se Z = X ou se existe
uma sequ¨eˆncia de regras X → Y1, Y1 → Y2, . . . , Yn → Z em R ,
n ≥ 0; no caso em que n = 0, tem-se apenas a regra X → Z . Ao
conjunto de todas as varia´veis encadeadas a X e´ dado o nome de
enc(X ).
Newton Jose´ Vieira Cap´ıtulo 3: Autoˆmatos de Pilha
Uma Introduc¸a˜o Informal
Autoˆmatos de Pilha Determin´ısticos
Autoˆmatos de Pilha Na˜o Determin´ısticos
Grama´ticas Livres do Contexto
Definic¸a˜o e exemplos
Derivac¸o˜es e ambiguidade
Manipulac¸a˜o de grama´ticas e formas normais
GLCs e autoˆmatos de pilha
Algoritmo para determinar varia´veis encadeadas
Algoritmo que determina enc(X ):
Entrada: (1) uma GLC G = (V ,Σ,R,P), e
(2) uma varia´vel X ∈ V .
Sa´ıda: enc(X ).
U ← ∅; N ← {X};
repita
U ← U ∪N ;
N ← {Y 6∈ U |Z → Y ∈ R para algum Z ∈ N}
ate´ N = ∅
retorne U .
Newton Jose´ Vieira Cap´ıtulo 3: Autoˆmatos de Pilha
Uma Introduc¸a˜o Informal
Autoˆmatos de Pilha Determin´ısticos
Autoˆmatos de Pilha Na˜o Determin´ısticos
Grama´ticas Livres do Contexto
Definic¸a˜o e exemplos
Derivac¸o˜es e ambiguidade
Manipulac¸a˜o de grama´ticas e formas normais
GLCs e autoˆmatos de pilha
Eliminando regras unita´rias
Uma GLC equivalente a G = (V ,Σ,R ,P), sem regras unita´rias, e´
G ′ = (V ,Σ,R ′,P), em que
R ′ = {X → w | existe Y ∈ enc(X ) tal que Y → w ∈ R e w 6∈ V }.
Newton Jose´ Vieira Cap´ıtulo 3: Autoˆmatos de Pilha
Uma Introduc¸a˜o Informal
Autoˆmatos de Pilha Determin´ısticos
Autoˆmatos de Pilha Na˜o Determin´ısticos
Grama´ticas Livres do Contexto
Definic¸a˜o e exemplos
Derivac¸o˜es e ambiguidade
Manipulac¸a˜o de grama´ticas e formas normais
GLCs e autoˆmatos de pilha
Exemplo/eliminac¸a˜o de regras unita´rias
GLC para expresso˜es aritme´ticas:
E → E+T |T
T → T∗F |F
F → (E ) | t
Os conjuntos enc(X ) para cada varia´vel X sa˜o:
enc(E ) = {E ,T ,F};
enc(T ) = {T ,F};
enc(F ) = {F}.
GLC equivalente, sem regras unita´rias:
E → E+T |T∗F | (E ) | t
T → T∗F | (E ) | t
F → (E ) | t
Newton Jose´ Vieira Cap´ıtulo 3: Autoˆmatos de Pilha
Uma Introduc¸a˜o Informal
Autoˆmatos de Pilha Determin´ısticos
Autoˆmatos de Pilha Na˜o Determin´ısticos
Grama´ticas Livres do Contexto
Definic¸a˜o e exemplos
Derivac¸o˜es e ambiguidade
Manipulac¸a˜o de grama´ticas e formas normais
GLCs e autoˆmatos de pilha
Interac¸a˜o entre os me´todos de eliminac¸a˜o
a) Ao se eliminar regras λ podem aparecer regras unita´rias.
Exemplo: GLC com as regras A→ BC e B → λ.
b) Ao se eliminar regras unita´rias podem aparecer regras λ.
Exemplo: GLC com P → λ, sendo P e´ o s´ımbolo de partida, e
a regra A→ P .
c) Ao se eliminar regras λ podem aparecer varia´veis inu´teis.
Exemplo: o do item (a), caso B → λ seja a u´nica regra B .
d) Ao se eliminar regras unita´rias podem aparecer varia´veis
inu´teis. Exemplo: GLC que conte´m A→ B e B na˜o aparece
do lado direito de nenhuma outra regra (B torna-se inu´til).
Ao se eliminar varia´veis inu´teis, na˜o podem aparecer novas regras.
Newton Jose´ Vieira Cap´ıtulo 3: Autoˆmatos de Pilha
Uma Introduc¸a˜o Informal
Autoˆmatos de Pilha Determin´ısticos
Autoˆmatos de Pilha Na˜o Determin´ısticos
Grama´ticas Livres do Contexto
Definic¸a˜o e exemplos
Derivac¸o˜es e ambiguidade
Manipulac¸a˜o de grama´ticas e formas normais
GLCs e autoˆmatos de pilha
Garantido consisteˆncia das eliminac¸o˜es
A seguinte sequeˆncia de eliminac¸o˜es para G = (V ,Σ,R ,P):
1 adicionar a regra P ′ → P , se P for recursivo;
2 eliminar regras λ;
3 eliminar regras unita´rias;
4 eliminar s´ımbolos inu´teis.
produz uma GLC equivalente cujas regras sa˜o das formas:
P → λ se λ ∈ L(G );
X → a para a ∈ Σ;
X → w para |w | ≥ 2.
Newton Jose´ Vieira Cap´ıtulo 3: Autoˆmatos de Pilha
Uma Introduc¸a˜o Informal
Autoˆmatos de Pilha Determin´ısticos
Autoˆmatos de Pilha Na˜o Determin´ısticos
Grama´ticas Livres do Contexto
Definic¸a˜o e exemplos
Derivac¸o˜es e ambiguidade
Manipulac¸a˜o de grama´ticas e formas normais
GLCs e autoˆmatos de pilha
Grama´tica na forma normal de Chomsky
Forma normal de Chomsky
Uma GLC G = (V ,Σ,R ,P) esta´ na forma normal de Chomsky
(FNC) se cada uma de suas regras tem uma das formas:
P → λ se λ ∈ L(G );
X → YZ para Y ,Z ∈ V;
X → a para a ∈ Σ.
Newton Jose´ Vieira Cap´ıtulo 3: Autoˆmatos de Pilha
Uma Introduc¸a˜o Informal
Autoˆmatos de Pilha Determin´ısticos
Autoˆmatos de Pilha Na˜o Determin´ısticos
Grama´ticas Livres do Contexto
Definic¸a˜o e exemplos
Derivac¸o˜es e ambiguidade
Manipulac¸a˜o de grama´ticas e formas normais
GLCs e autoˆmatos de pilha
Transformac¸a˜o para a forma normal de Chomsky
Seja uma GLC G . Obter uma GLC equivalente a G tal que:
P → λ se λ ∈ L(G );
X → a para a ∈ Σ;
X → w para |w | ≥ 2.
Mais dois passos:
1 Modificar cada regra X → w , |w | ≥ 2, de forma que ela fique
contendo apenas varia´veis.
2 Substituir cada regra X → Y1Y2 . . .Yn, n ≥ 3, em que cada
Yi e´ uma varia´vel, pelo conjunto das regras: X → Y1Z1,
Z1 → Y2Z2, . . . , Zn−2 → Yn−1Yn, em que Z1, Z2, . . . , Zn−2
sa˜o varia´veis novas.
Newton Jose´ Vieira Cap´ıtulo 3: Autoˆmatos de Pilha
Uma Introduc¸a˜o Informal
Autoˆmatos de Pilha Determin´ısticos
Autoˆmatos de Pilha Na˜o Determin´ısticos
Grama´ticas Livres do Contexto
Definic¸a˜o e exemplos
Derivac¸o˜es e ambiguidade
Manipulac¸a˜o de grama´ticas e formas normais
GLCs e autoˆmatos de pilha
Exemplo/obtenc¸a˜o de grama´tica na FNC
Seja a GLC G :
L → (S)
S → SE |λ
E → a | L
Apo´s a eliminac¸a˜o de regras λ:
L → (S) | ()
S → SE |E
E → a | L
Como enc(L) = {L}, enc(S) = {S ,E , L} e enc(E ) = {E , L}:
L → (S) | ()
S → SE | a | (S) | ()
E → a | (S) | ()
Newton Jose´ Vieira Cap´ıtulo 3: Autoˆmatos de Pilha
Uma Introduc¸a˜o Informal
Autoˆmatos de Pilha Determin´ısticos
Autoˆmatos de Pilha Na˜o Determin´ısticos
Grama´ticas Livres do Contexto
Definic¸a˜o e exemplos
Derivac¸o˜es e ambiguidade
Manipulac¸a˜o de grama´ticas e formas normais
GLCs e autoˆmatos de pilha
Exemplo/obtenc¸a˜o de grama´tica na FNC(cont.)
L → (S) | ()
S → SE | a | (S) | ()
E → a | (S) | ()
Finalmente:
L → AX |AB
S → SE | a |AX |AB
E → a |AX |AB
X → SB
A → (
B → )
Newton Jose´ Vieira Cap´ıtulo 3: Autoˆmatos de Pilha
Uma Introduc¸a˜o Informal
Autoˆmatos de Pilha Determin´ısticos
Autoˆmatos de Pilha Na˜o Determin´ısticos
Grama´ticas Livres do Contexto
Definic¸a˜o e exemplos
Derivac¸o˜es e ambiguidade
Manipulac¸a˜o de grama´ticas e formas normais
GLCs e autoˆmatos de pilha
Eliminac¸a˜ode regras recursivas a` esquerda
Sejam as regras, a seguir, todas as regras X de uma GLC G :
X → Xy1 |Xy2 | . . . |Xyn |w1 |w2 | . . . |wk
em que nenhum wi comec¸a com X .
Utilizando recursa˜o a` direita, em vez de recursa˜o a` esquerda:
X → w1Z |w2Z | . . . |wkZ
Z → y1Z | y2Z | . . . | ynZ |λ
em que Z e´ uma varia´vel nova. Eliminado-se a regra λ:
X → w1Z |w2Z | . . . |wkZ |w1 |w2 | . . . |wk
Z → y1Z | y2Z | . . . | ynZ | y1 | y2 | . . . | yn
Newton Jose´ Vieira Cap´ıtulo 3: Autoˆmatos de Pilha
Uma Introduc¸a˜o Informal
Autoˆmatos de Pilha Determin´ısticos
Autoˆmatos de Pilha Na˜o Determin´ısticos
Grama´ticas Livres do Contexto
Definic¸a˜o e exemplos
Derivac¸o˜es e ambiguidade
Manipulac¸a˜o de grama´ticas e formas normais
GLCs e autoˆmatos de pilha
Exemplo/eliminac¸a˜o de regras recursivas a` esquerda
G :
E → E+E |E∗E | (E ) | t
Retirando-se recursa˜o a` esquerda:
E → (E )Z | tZ
Z → +EZ | ∗EZ |λ
Newton Jose´ Vieira Cap´ıtulo 3: Autoˆmatos de Pilha
Uma Introduc¸a˜o Informal
Autoˆmatos de Pilha Determin´ısticos
Autoˆmatos de Pilha Na˜o Determin´ısticos
Grama´ticas Livres do Contexto
Definic¸a˜o e exemplos
Derivac¸o˜es e ambiguidade
Manipulac¸a˜o de grama´ticas e formas normais
GLCs e autoˆmatos de pilha
Exemplo/eliminac¸a˜o de varia´vel em regra
Seja G = (V ,Σ,R ,P) tal que X → uYv ∈ R , Y ∈ V e Y 6= X .
Sejam Y→ w1|w2| . . . |wn todas as regras Y em R .
R pode ser substitu´ıda por
(R − {X → uYv}) ∪ {X → uw1v | uw2v | . . . | uwnv}.
Newton Jose´ Vieira Cap´ıtulo 3: Autoˆmatos de Pilha
Uma Introduc¸a˜o Informal
Autoˆmatos de Pilha Determin´ısticos
Autoˆmatos de Pilha Na˜o Determin´ısticos
Grama´ticas Livres do Contexto
Definic¸a˜o e exemplos
Derivac¸o˜es e ambiguidade
Manipulac¸a˜o de grama´ticas e formas normais
GLCs e autoˆmatos de pilha
Grama´tica na forma normal de Greibach
Forma normal de Greibach
Uma GLC G = (V ,Σ,R ,P) esta´ na forma normal de Greibach
(FNG) se cada uma de suas regras tem uma das formas:
P → λ se λ ∈ L(G );
X → ay para a ∈ Σ e y ∈ V ∗.
Uma forma sentencial de uma grama´tica na FNG, com excec¸a˜o de
λ, e´ da forma xy , em que x ∈ Σ+ e y ∈ V ∗.
Qual o tamanho de uma derivac¸a˜o de uma palavra?
Newton Jose´ Vieira Cap´ıtulo 3: Autoˆmatos de Pilha
Uma Introduc¸a˜o Informal
Autoˆmatos de Pilha Determin´ısticos
Autoˆmatos de Pilha Na˜o Determin´ısticos
Grama´ticas Livres do Contexto
Definic¸a˜o e exemplos
Derivac¸o˜es e ambiguidade
Manipulac¸a˜o de grama´ticas e formas normais
GLCs e autoˆmatos de pilha
Transformac¸a˜o para a forma normal de Greibach
Seja uma GLC G . Obter uma GLC equivalente a G tal que:
P → λ se λ ∈ L(G );
X → a para a ∈ Σ;
X → w para |w | ≥ 2.
Em seguida:
Para cada X → w para |w | ≥ 2, substituir por varia´veis todos
os terminais de w , a partir de seu segundo s´ımbolo. Com isso,
obteˆm-se regras da forma X → Yy , sendo que Y ∈ V ∪ Σ e
y ∈ V+.
Newton Jose´ Vieira Cap´ıtulo 3: Autoˆmatos de Pilha
Uma Introduc¸a˜o Informal
Autoˆmatos de Pilha Determin´ısticos
Autoˆmatos de Pilha Na˜o Determin´ısticos
Grama´ticas Livres do Contexto
Definic¸a˜o e exemplos
Derivac¸o˜es e ambiguidade
Manipulac¸a˜o de grama´ticas e formas normais
GLCs e autoˆmatos de pilha
Transformac¸a˜o para a FNG (cont.)
Numerar sequencialmente as varia´veis (#P = 1).
Para cada A ∈ V , comec¸ando com P , na ordem dada pela
numerac¸a˜o, fazer enquanto poss´ıvel:
1 Se existe A→ By , para |y | ≥ 1, tal que #A > #B , substituir
B .
2 Se existe A→ Ay , para |y | ≥ 1, eliminar a recursa˜o a`
esquerda.
Seja B a varia´vel de maior nu´mero em que ha´ regra da forma
B → Cy , com C ∈ V . Substituir C . Repetir ate´ ser atingida a
varia´vel P .
Para regras da forma Z → Ay , em que Z e´ varia´vel nova
criada eliminando-se recursa˜o a` esquerda, substituir A.
Newton Jose´ Vieira Cap´ıtulo 3: Autoˆmatos de Pilha
Uma Introduc¸a˜o Informal
Autoˆmatos de Pilha Determin´ısticos
Autoˆmatos de Pilha Na˜o Determin´ısticos
Grama´ticas Livres do Contexto
Definic¸a˜o e exemplos
Derivac¸o˜es e ambiguidade
Manipulac¸a˜o de grama´ticas e formas normais
GLCs e autoˆmatos de pilha
Exemplo/transformac¸a˜o para a FNG
G :
A → CB
B → BBD | b
C → BBC |Dc
D → AD | d
Elimina-se C → Dc e introduz-se C → DE e E → c.
Numerac¸a˜o: #A = 1, #B = 2, #C = 3, #D = 4 e #E = 5.
A → CB
∗ B → b | bZ1
C → BBC |DE
D → AD | d
E → c
∗ Z1 → BD |BDZ1
Newton Jose´ Vieira Cap´ıtulo 3: Autoˆmatos de Pilha
Uma Introduc¸a˜o Informal
Autoˆmatos de Pilha Determin´ısticos
Autoˆmatos de Pilha Na˜o Determin´ısticos
Grama´ticas Livres do Contexto
Definic¸a˜o e exemplos
Derivac¸o˜es e ambiguidade
Manipulac¸a˜o de grama´ticas e formas normais
GLCs e autoˆmatos de pilha
Exemplo/transformac¸a˜o para a FNG (cont.)
Substituindo-se a regra C → BBC (#C > #B):
A → CB
B → b | bZ1
* C → bBC | bZ1BC
C → DE
D → AD | d
E → c
Z1 → BD |BDZ1
Substituindo-se a regra D → AD (#D > #A):
A → CB
B → b | bZ1
C → bBC | bZ1BC |DE
* D → CBD
D → d
E → c
Z1 → BD |BDZ1
Newton Jose´ Vieira Cap´ıtulo 3: Autoˆmatos de Pilha
Uma Introduc¸a˜o Informal
Autoˆmatos de Pilha Determin´ısticos
Autoˆmatos de Pilha Na˜o Determin´ısticos
Grama´ticas Livres do Contexto
Definic¸a˜o e exemplos
Derivac¸o˜es e ambiguidade
Manipulac¸a˜o de grama´ticas e formas normais
GLCs e autoˆmatos de pilha
Exemplo/transformac¸a˜o para a FNG (cont.)
Substituindo-se a regra D → CBD (#D > #C ):
A → CB
B → b | bZ1
C → bBC | bZ1BC |DE
* D → bBCBD | bZ1BCBD |DEBD
D → d
E → c
Z1 → BD |BDZ1
Eliminando-se a recursa˜o a` esquerda para as regras D:
A → CB
B → b | bZ1
C → bBC | bZ1BC |DE
* D → bBCBD | bZ1BCBD | d | bBCBDZ2 | bZ1BCBDZ2 | dZ2
E → c
Z1 → BD |BDZ1
* Z2 → EBD |EBDZ2
Newton Jose´ Vieira Cap´ıtulo 3: Autoˆmatos de Pilha
Uma Introduc¸a˜o Informal
Autoˆmatos de Pilha Determin´ısticos
Autoˆmatos de Pilha Na˜o Determin´ısticos
Grama´ticas Livres do Contexto
Definic¸a˜o e exemplos
Derivac¸o˜es e ambiguidade
Manipulac¸a˜o de grama´ticas e formas normais
GLCs e autoˆmatos de pilha
Exemplo/transformac¸a˜o para a FNG (cont.)
Substituindo-se C → DE :
A → CB
B → b | bZ1
C → bBC | bZ1BC
* C → bBCBDE | bZ1BCBDE | dE | bBCBDZ2E
| bZ1BCBDZ2E | dZ2E
D → bBCBD | bZ1BCBD | d | bBCBDZ2 | bZ1BCBDZ2 | dZ2
E → c
Z1 → BD |BDZ1
Z2 → EBD |EBDZ2
Newton Jose´ Vieira Cap´ıtulo 3: Autoˆmatos de Pilha
Uma Introduc¸a˜o Informal
Autoˆmatos de Pilha Determin´ısticos
Autoˆmatos de Pilha Na˜o Determin´ısticos
Grama´ticas Livres do Contexto
Definic¸a˜o e exemplos
Derivac¸o˜es e ambiguidade
Manipulac¸a˜o de grama´ticas e formas normais
GLCs e autoˆmatos de pilha
Exemplo/transformac¸a˜o para a FNG (cont.)
Substituindo-se A→ CB :
* A → bBCB | bZ1BCB | bBCBDEB | bZ1BCBDEB | dEB
| bBCBDZ2EB | bZ1BCBDZ2EB | dZ2EB
B → b | bZ1
C → bBC | bZ1BC | bBCBDE | bZ1BCBDE
| dE | bBCBDZ2E | bZ1BCBDZ2E | dZ2E
D → bBCBD | bZ1BCBD | d | bBCBDZ2 | bZ1BCBDZ2 | dZ2
E → c
Z1 → BD |BDZ1
Z2 → EBD |EBDZ2
Newton Jose´ Vieira Cap´ıtulo 3: Autoˆmatos de Pilha
Uma Introduc¸a˜o Informal
Autoˆmatos de Pilha Determin´ısticos
Autoˆmatos de Pilha Na˜o Determin´ısticos
Grama´ticas Livres do Contexto
Definic¸a˜o e exemplos
Derivac¸o˜es e ambiguidade
Manipulac¸a˜o de grama´ticas e formas normais
GLCs e autoˆmatos de pilha
Exemplo/transformac¸a˜o para a FNG (cont.)
Finalmente, substitui-se as regras introduzidas por eliminac¸a˜o de
recursa˜o a` esquerda:
A → bBCB | bZ1BCB | bBCBDEB | bZ1BCBDEB | dEB
| bBCBDZ2EB | bZ1BCBDZ2EB | dZ2EB
B → b | bZ1
C → bBC | bZ1BC | bBCBDE | bZ1BCBDE
| dE | bBCBDZ2E | bZ1BCBDZ2E | dZ2E
D → bBCBD | bZ1BCBD | d | bBCBDZ2 | bZ1BCBDZ2 | dZ2
E → c
* Z1 → bD | bZ1D | bDZ1 | bZ1DZ1
* Z2 → cBD | cBDZ2
Newton Jose´ Vieira Cap´ıtulo 3: Autoˆmatosde Pilha
Uma Introduc¸a˜o Informal
Autoˆmatos de Pilha Determin´ısticos
Autoˆmatos de Pilha Na˜o Determin´ısticos
Grama´ticas Livres do Contexto
Definic¸a˜o e exemplos
Derivac¸o˜es e ambiguidade
Manipulac¸a˜o de grama´ticas e formas normais
GLCs e autoˆmatos de pilha
Obtenc¸a˜o de AP a partir de GLC
Seja G ′ = (V ,Σ,R ,P) uma GLC na FNG equivalente a G .
APN que aceita L(G ′):
-
�
�
�
�i
-λ, λ/P
�
�
�
�
�
�
�
f
��ff λ,P/λ, se P → λ ∈ Ra,X/y , se X → ay ∈ R
Newton Jose´ Vieira Cap´ıtulo 3: Autoˆmatos de Pilha
Uma Introduc¸a˜o Informal
Autoˆmatos de Pilha Determin´ısticos
Autoˆmatos de Pilha Na˜o Determin´ısticos
Grama´ticas Livres do Contexto
Definic¸a˜o e exemplos
Derivac¸o˜es e ambiguidade
Manipulac¸a˜o de grama´ticas e formas normais
GLCs e autoˆmatos de pilha
Obtenc¸a˜o de AP a partir de GLC/Exemplo
Seja G = ({P}, {0, 1},R ,P), em que R consta das regras:
P → 0P1P | 1P0P |λ
Uma GLC equivalente na FNG:
P → 0PUP | 1PZP |λ
Z → 0
U → 1
Um AP que reconhece L(G ):
-
�
�
�
�i
-λ, λ/P
�
�
�
�
�
�
�
f
��ff
λ, P/λ
0, P/PUP
1, P/PZP
0, Z/λ
1, U/λ
Newton Jose´ Vieira Cap´ıtulo 3: Autoˆmatos de Pilha
Uma Introduc¸a˜o Informal
Autoˆmatos de Pilha Determin´ısticos
Autoˆmatos de Pilha Na˜o Determin´ısticos
Grama´ticas Livres do Contexto
Definic¸a˜o e exemplos
Derivac¸o˜es e ambiguidade
Manipulac¸a˜o de grama´ticas e formas normais
GLCs e autoˆmatos de pilha
Obtenc¸a˜o de GLC a partir de AP
A ide´ia:
Seja um APN M = (E ,Σ, Γ, δ, I ,F ). Dados e, e ′ ∈ E e
X ∈ Γ ∪ {λ}:
C (e,X , e ′) = {w ∈ Σ∗ | [e,w ,X ]
∗
⊢ [e ′, λ, λ]}.
Enta˜o:
L(M) =
⋃
(i ,f )∈I×F
C (i , λ, f ).
Obtenc¸a˜o da GLC:
1 Criar regras P → [i , λ, f ], para cada i ∈ I e f ∈ F .
2 Criar regras para varia´veis [e,X , e ′], de tal forma que de
[e,X , e ′] se gere o conjunto C (e,X , e ′).
Newton Jose´ Vieira Cap´ıtulo 3: Autoˆmatos de Pilha
Uma Introduc¸a˜o Informal
Autoˆmatos de Pilha Determin´ısticos
Autoˆmatos de Pilha Na˜o Determin´ısticos
Grama´ticas Livres do Contexto
Definic¸a˜o e exemplos
Derivac¸o˜es e ambiguidade
Manipulac¸a˜o de grama´ticas e formas normais
GLCs e autoˆmatos de pilha
Obtenc¸a˜o de GLC a partir de AP/Exemplo
Seja o APD:
-
�
�
�
�
�
�
�
0
��
?
a, λ/X
-c, λ/λ
�
�
�
�
�
�
�
1
��
?
b, X/λ
Primeiras regras:
P → [0, λ, 0] | [0, λ, 1]
Regras [0, λ, 0]:
[0, λ, 0] → λ
[0, λ, 0] → a[0, X, 0]
[0, λ, 0] → c[1, λ, 0]
As varia´veis [0, X, 0] e [1, λ, 0] sa˜o inu´teis!
Como sa˜o as outras regras?
Newton Jose´ Vieira Cap´ıtulo 3: Autoˆmatos de Pilha