Árvore de Derivação Simplificação Ambigüidade e Formas Normais

Prévia do material em texto

P
rof
.
 Y
a
nd
re
 M
ald
o
n
ad
o
 
-1
Gramática Livre de 
Contexto
Prof. Yandre Maldonado e Gomes da Costa
yandre@din.uem.br
•Árvore de derivação
•Ambigüidade
•Simplificação de Gramática
•Forma Normal de Chomsky (FNC)
•Forma Normal de Greibach (FNG)
P
rof
.
 Y
a
nd
re
 M
ald
o
n
ad
o
 
-2
Árvore de Derivação
� Uma maneira de representar a derivação 
de uma sentença a partir de uma GLC;
� Particularmente útil em algumas aplicações, 
como compiladores;
� Em uma árvore de derivação:
� A raiz é o símbolo de partida da GLC;
� Os nós internos são símbolos de V;
� Os nós folha são símbolos de T (ou λ);
P
rof
.
 Y
a
nd
re
 M
ald
o
n
ad
o
 
-3
Árvore de Derivação
� Exemplo: árvore de derivação para a 
sentença “x+x*x” a partir da seguinte 
GLC;
1) E → E+E
2) E → E*E
3) E → (E)
4) E → x
E
E E
E E
+
*x
x x
E ⇒ E+E ⇒ x+E ⇒ x+E*E ⇒ x+x*E ⇒ x+x*x1 4 2 4 4
P
rof
.
 Y
a
nd
re
 M
ald
o
n
ad
o
 
-4
Ambigüidade
� Uma sentença é dita ambígua, 
quando existir pelo menos dois 
“caminhos de derivação” para ela;
� Assim, existe mais do que uma árvore 
de derivação associada a uma 
sentença ambígua;
� Uma gramática é dita ambígua, se ela 
produzir pelo menos uma sentença de 
forma ambígua;
P
rof
.
 Y
a
nd
re
 M
ald
o
n
ad
o
 
-5
Ambigüidade
� Exemplo: dois caminhos para “x+x*x”
1) E → E+E
2) E → E*E
3) E → (E)
4) E → x
E
E E
E E
+
*x
x x
E ⇒ E+E ⇒ x+E ⇒ x+E*E ⇒ x+x*E ⇒ x+x*x1 4 2 4 4
E
E E
E E
*
+ x
x x
E ⇒ E*E ⇒ E+E*E ⇒ x+E*E ⇒ x+x*E ⇒ x+x*x2 1 4 4 4
P
rof
.
 Y
a
nd
re
 M
ald
o
n
ad
o
 
-6
Simplificação de GLC
� É possível simplificar algumas 
produções de uma GLC sem reduzir o 
seu poder de geração;
� Tipos de simplificação:
� Exclusão de símbolos inúteis;
� Exclusão de produções vazias;
� Exclusão de produções da forma A→B;
P
rof
.
 Y
a
nd
re
 M
ald
o
n
ad
o
 
-7
Simplificação de GLC
� Exclusão de símbolos inúteis:
� Variáveis (não-terminais) ou terminais 
que não contribuem com a produção 
de sentenças;
� Etapas:
• Exclusão de símbolos improdutivos;
• Exclusão de símbolos inacessíveis;
P
rof
.
 Y
a
nd
re
 M
ald
o
n
ad
o
 
-8
Simplificação de GLC
� Exclusão de símbolos inúteis:
� É importante por vários motivos
• Em gramáticas grandes, como 
gramáticas de linguagens de 
programação, pode acontecer de se 
esquecer de definir regras relativas a 
alguma variável, ou então, uma variável, 
apesar de ter suas regras já definidas, 
pode não ter sido utilizada na formação 
de novas regras.
P
rof
.
 Y
a
nd
re
 M
ald
o
n
ad
o
 
-9
Simplificação de GLC
1) S → AB | a
2) B → b
3) C → c
EXEMPLO: Seja a Gramática
({S, A, B, C}, {a, b, c}, P,S} onde P contém as regras:
1) S → a
C é inútil (não é acessível)
A é inútil (não está definido) 
B é inútil (não usado em palavras da linguagem)
Eliminando-se as variáveis inúteis e as regras 
que as referenciam, além dos terminais b e c 
que não ocorrem em nenhuma regra (não são 
usados para formar palavras da linguagem 
gerada) tem-se esta regra
A Gramática equivalente é dada por
({S}, {a}, S → a, S}
P
rof
.
 Y
a
nd
re
 M
ald
o
n
ad
o
 
-10
Simplificação de GLC
� Etapa 1: garante que qualquer não terminal 
gera terminais;
� Algoritmo: parte de G(V,T,P,S) e dá origem 
a G1(V1,T,P1,S);
� Construção de V1:
� Conjunto P1: P menos as produções cujos 
não terminais não pertencem a V1;
V1 = ∅
repita V1 = V1∪ {A | A → α e α ϵ (T ∪ V1 )*}
até que o cardinal de V1 não aumente;
P
rof
.
 Y
a
nd
re
 M
ald
o
n
ad
o
 
-11
Simplificação de GLC
� Exemplo:
1) S → aAa
2) S → bBb
3) A → a
4) A → S
5) C → c
6) B → bB
V1 = ∅
repita
V1 = V1∪ {A | A → α e α ϵ (T ∪ V1 )*}
até que o cardinal de V1 não aumente;
{A, C, S}3
{A, C, S}2
{A, C}1
∅início
V1iteração
1) S → aAa
2) A → a
3) A → S
4) C → c
Qqr não 
terminal 
gera 
terminal
P
rof
.
 Y
a
nd
re
 M
ald
o
n
ad
o
 
-12
Simplificação de GLC
� Etapa 2: garante que qualquer símbolo é
atingível a partir do símbolo inicial;
� Algoritmo: parte de G1(V1,T1,P1,S) e dá
origem a G2(V2,T2,P2,S);
� Conjunto P2: P1 menos as produções cujos 
símbolos não pertencem a V2 ou T2;
T2 = ∅; V2 = {S};
repita V2 = V2∪ {A | X → αAβ ϵ P1 , X ϵ V2};
T2 = T2∪ {a | X → αaβ ϵ P1 , X ϵ V2};
até que os cardinais de V2 e T2 não aumentem;
P
rof
.
 Y
a
nd
re
 M
ald
o
n
ad
o
 
-13
Simplificação de GLC
� Exemplo:
1) S → aAa
2) A → a
3) A → S
4) C → c
T2 = ∅; V2 = {S};
repita V2 = V2∪ {A | X → αAβ ϵ P1 , X ϵ V2};
T2 = T2∪ {a | X → αaβ ϵ P1 , X ϵ V2};
até que os cardinais de V2 e T2 não aumentem;
{a}{S, A}2
{a}{S, A}1
∅{S}início
terminaisvariáveisiteração
1) S → aAa
2) A → a
3) A → S
P
rof
.
 Y
a
nd
re
 M
ald
o
n
ad
o
 
-14
Simplificação de GLC
� Exclusão de produções vazias:
� Produções vazias são produções da 
forma A → λ;
� Etapas:
• Variáveis que constituem produções 
vazias;
• Exclusão das produções vazias;
• Inclusão da geração da palavra vazia, se 
necessário;
P
rof
.
 Y
a
nd
re
 M
ald
o
n
ad
o
 
-15
Simplificação de GLC
� Etapa 1: conjunto de variáveis que 
constituem produções vazias;
� Considera inicialmente todas as variáveis 
que geram diretamente λ;
� A seguir, sucessivamente são determinadas 
as variáveis que indiretamente geram λ;
� Algoritmo:
Vλ = { A | A → λ };
repita
Vλ = Vλ∪ { X | X→X1…Xn ϵ P | X1, …, Xn ϵ Vλ }
até que o cardinal de Vλ não aumente;
P
rof
.
 Y
a
nd
re
 M
ald
o
n
ad
o
 
-16
Simplificação de GLC
� Exemplo:
1) S → aXa
2) S → bXb
3) S → λ
4) X → a
5) X → b
6) X → Y
7) Y → λ
{S, Y, X}2
{S, Y, X}1
{S, Y}início
Vλiteração
Vλ = { A | A → λ };
repita
Vλ = Vλ∪ { X | X→X1…Xn ϵ P | X1, …, Xn ϵ Vλ }
até que o cardinal de Vλ não aumente;
P
rof
.
 Y
a
nd
re
 M
ald
o
n
ad
o
 
-17
Simplificação de GLC
� Etapa 2: conjunto de produções sem 
produções vazias;
� Algoritmo: parte de G(V,T,P,S) e dá origem 
a G1(V,T,P1,S);
P1 = {A → α | α ≠ λ};
repita
para toda
A → α ϵ P1 e X ϵ Vλ | α = α1Xα2 e α1α2 ≠ λ
faca
P1 = P1 ∪ { A → α1 α2 }
até que o cardinal de P1 não aumente;
P
rof
.
 Y
a
nd
re
 M
ald
o
n
ad
o
 
-18
Simplificação de GLC
� Exemplo:
1) S → aXa
2) S → bXb
3) S → λ
4) X → a
5) X → b
6) X → Y
7) Y → λ
{S → aXa | bXb | aa | bb, X → a | b | Y}2
{S → aXa | bXb | aa | bb, X → a | b | Y}1
{S → aXa | bXb, X → a | b | Y}inicial
produçõesiteração
Resultado da etapa 1: Vλ = {S, Y, X}
P1 = {A → α | α ≠ λ};
repita
para toda
A → α ϵ P1 e X ϵ Vλ | α = α1Xα2 e α1α2 ≠ λ
faca
P1 = P1 ∪ { A → α1 α2 }
até que o cardinal de P1 não aumente;
1) S → aXa
2) S → bXb
3) S → aa
4) S → bb
5) X → a
6) X → b
7) X → Y
P
rof
.
 Y
a
nd
re
 M
ald
o
n
ad
o
 
-19
Simplificação de GLC
� Etapa 3: quando a palavra vazia pertencer 
à linguagem gerada pela gramática, uma 
regra do tipo S → λ deve ser incluída em P;
Etapa 1:
1) S → aXa
2) S → bXb
3) S → λ
4) X → a
5) X → b
6) X → Y
7) Y → λ
Resultado: Vλλλλ = {S, Y, X}
Etapa 2:
1) S → aXa
2) S → bXb
3) S → aa
4) S → bb
5) X → a
6) X → b
7) X → Y
Etapa 3:
1) S → aXa
2) S → bXb
3) S → aa
4) S → bb
5) S → λ
6) X → a
7) X → b
8) X → Y
Note que Y se tornou inútil
P
rof
.
 Ya
nd
re
 M
ald
o
n
ad
o
 
-20
Simplificação de GLC
� Exemplo:
1) P → APB | C
2) A → AaaA | λ
3) B → BBb | C
4) C → cC | λ
1) P → APB | AB | AP | PB | A | B | C | λ
2) A → AaaA | aaA | Aaa | aa
3) B → BBb | Bb | b | C
4) C → cC | c
{A, C, P, B}1
{A, C}início
Vλiteração
P
rof
.
 Y
a
nd
re
 M
ald
o
n
ad
o
 
-21
Simplificação de GLC
� Exemplo:
1) P → BPA | A
2) A → aA | λ
3) B → Bba | λ
1) P → BPA | PA | BP | BA | B | A | λ
2) A → aA | a 
3) B → Bba | ba
{A, B, P}1
{A, B}início
Vλiteração
P
rof
.
 Y
a
nd
re
 M
ald
o
n
ad
o
 
-22
Simplificação de GLC
� Exclusão de produções da forma A → B:
� Produções da forma A → B não 
adicionam informação sintática alguma;
� Etapas:
• Construção do fecho de cada variável;
• Exclusão das produções da forma A → B;
P
rof
.
 Y
a
nd
re
 M
ald
o
n
ad
o
 
-23
Simplificação de GLC
� Etapa 1: construção do fecho de cada 
variável;
� Algoritmo:
para toda A ϵ V 
faça FECHO-A = { B | A≠B e A ⇒*B} usando
exclusivamente produções da forma X → Y;
P
rof
.
 Y
a
nd
re
 M
ald
o
n
ad
o
 
-24
Simplificação de GLC
� Exemplo:
1) S → aXa
2) S → bXb
3) X → a
4) X → b
5) X → S
6) X → λ {S}Fecho-X
∅Fecho-S
para toda A ϵ V 
faça FECHO-A = { B | A≠B e A ⇒*B} usando
exclusivamente produções da forma X → Y;
P
rof
.
 Y
a
nd
re
 M
ald
o
n
ad
o
 
-25
Simplificação de GLC
� Etapa 2: exclusão das produções da forma 
A → B;
� Algoritmo: parte de G(V,T,P,S) e dá origem 
a G1(V,T,P1,S);
P1 = { A → α | α ∉ V };
para toda A ϵ V e B ϵ FECHO-A
faça se B → α ϵ P e α ∉ V
então P1 = P1 ∪ {A → α};
P
rof
.
 Y
a
nd
re
 M
ald
o
n
ad
o
 
-26
Simplificação de GLC
� Exemplo:
1) S → aXa
2) S → bXb
3) X → a
4) X → b
5) X → S
6) X → λ
{S → aXa | bXb, X → a | b | λ | aXa | bXb}X
{S → aXa | bXb, X → a | b | λ}S
{S → aXa | bXb, X → a | b | λ}Inicial
produçõesiteração
Etapa 1: Fecho-S=∅ e Fecho-X={S}
P1 = { A → α | α ∉ V };
para toda A ϵ V e B ϵ FECHO-A
faça se B → α ϵ P e α ∉ V
então P1 = P1 ∪ {A → α};
1) S → aXa
2) S → bXb
3) X → a
4) X → b
6) X → λ
7) X → aXa
8) X → bXb
P
rof
.
 Y
a
nd
re
 M
ald
o
n
ad
o
 
-27
Simplificação de GLC
� Simplificações combinadas:
� A eliminação de produções vazias pode 
gerar símbolos inúteis;
� A eliminação de produções unitárias (X → Y) 
também pode gerar símbolos inúteis;
� Por isso, em simplificações combinadas 
recomenda-se a seguinte seqüência:
• Exclusão de Produções Vazias;
• Exclusão de Produções Unitárias;
• Exclusão de Símbolos Inúteis;
P
rof
.
 Y
a
nd
re
 M
ald
o
n
ad
o
 
-28
Formas Normais
� As formas normais estabelecem 
restrições rígidas a formação das 
regras em uma GLC sem diminuir o 
poder de representação deste tipo de 
gramática;
� Muito utilizadas em algoritmos de 
reconhecimento, transformações e 
prova de teoremas;
P
rof
.
 Y
a
nd
re
 M
ald
o
n
ad
o
 
-29
Formas Normais
� As mais conhecidas são:
� Forma Normal de Chomsky (FNC);
� Forma Normal de Greibach (FNG);
� Na FNC, as regras devem ser da 
forma:
A → BC ou A → a
� Na FNG, as regras devem ser da 
forma:
A → aα
Sendo A, B e C ∈ V, a ∈ T e α ∈ V*
P
rof
.
 Y
a
nd
re
 M
ald
o
n
ad
o
 
-30
Forma Normal de Chomsky
� As regras devem ser da forma:
A → BC ou A → a
� O algoritmo é dividido em três etapas:
� Simplificação da gramática: exclusão de 
produções vazias e de produções unitárias, 
opcionalmente pode-se excluir símbolos 
inúteis;
� Transformação do lado direito de regras que 
tenham um comprimento maior ou igual a 2;
� Transformação do lado direito de regras que 
tenham um comprimento maior ou igual a 2 
em produções com exatamente 2 variáveis;
Chomsky, 1928
P
rof
.
 Y
a
nd
re
 M
ald
o
n
ad
o
 
-31
Forma Normal de Chomsky
� Etapa 1: simplificação da gramática;
� Excluir produções vazias;
� Excluir produções unitárias;
� Excluir símbolos inúteis (opcional);
� Exemplo:
1) E → E+E
2) E → E*E
3) E → (E)
4) E → x
A gramática já está simplificada.
P
rof
.
 Y
a
nd
re
 M
ald
o
n
ad
o
 
-32
Forma Normal de Chomsky
� Etapa 2: 
transformação do lado 
direito de regras com 
tamanho maior ou 
igual a 2;
� Faz com que esses 
lados direitos 
apresentem apenas 
não terminais;
� Algoritmo: parte de 
G1(V1,T,P1,S) e dá
origem a 
G2(V2,T,P2,S);
V2 = V1;
P2 = P1;
Para toda A → X1X2..Xn ϵ P2 tal que n >= 2
faça se para r ϵ {1, .., n}, Xr é terminal 
então (suponha Xr = a )
V2 = V2∪ {Ca};
susbstitui a por Ca em 
A → X1X2… Xn ϵ P2;
P2 = P2∪ {Ca→ a};
1) E → E+E
2) E → E*E
3) E → (E)
4) E → x
1) E → EC+E
2) E → EC
*
E
3) E → C(EC)
4) E → x
5) C+ → +
6) C
*
→ *
7) C( → (
8) C) → )
P
rof
.
 Y
a
nd
re
 M
ald
o
n
ad
o
 
-33
Forma Normal de Chomsky
� Etapa 3: transformação 
do lado direito das 
produções com tamanho 
maior ou igual a 3 em 
produções com 
exatamente 2 variáveis;
� Faz com que esses 
lados direitos 
apresentem exatamente 
2 variáveis;
� Algoritmo: parte de 
G2(V2,T,P2,S) e dá
origem a G3(V3,T,P3,S);
1) E → EC+E
2) E → EC
*
E
3) E → C(EC)
4) E → x
5) C+ → +
6) C
*
→ *
7) C( → (
8) C) → )
V3 = V2;
P3 = P2;
Para toda A → B1B2..Bn ϵ P3 tal que n >= 3
faça P3 = P3 – {A → B1B2 .. Bn};
V3 = V3∪ {D1, …, Dn-2};
P3 = P3∪ {A → B1D1, D1→ B2D2,…, 
Dn-3→ Bn-2Dn-2, Dn-2→
Bn-1Dn-1};
1) E → ED1
2) E → ED2
3) E → C(D3
4) E → x
5) C+ → +
6) C
*
→ *
7) C( → (
8) C) → )
9) D1 → C+E
10) D2 → C*E
11) D3 → EC)
P
rof
.
 Y
a
nd
re
 M
ald
o
n
ad
o
 
-34
Forma Normal de Chomsky
� Exemplo:
� Seja uma GLC G = ({L,S,E},{a, (,)}, P, L), 
onde P consta das regras:
1) L → (S)
2) S → SE | λ
3) E → a | L
P
rof
.
 Y
a
nd
re
 M
ald
o
n
ad
o
 
-35
Forma Normal de Chomsky
� Exemplo:
1) L → (S)
2) S → SE | λ
3) E → a | L
Observando-se que S é a única variável anulável, tem-se as 
seguintes regras após a eliminação de regra λ
1) L → (S) | ( )
2) S → SE | E
3) E → a | L
P
rof
.
 Y
a
nd
re
 M
ald
o
n
ad
o
 
-36
Forma Normal de Chomsky
� Exemplo:
1) L → (S) | ( )
2) S → SE | E
3) E → a | L
Obtem-se as seguintes regras após a eliminação de regras 
unitárias:
1) L → (S) | ( )
2) S → SE | a | (S) | ( )
3) E → a | (S) | ( )
Observando-se os 
fechos
Fecho(L)={}
Fecho(S)={E,L}
Fecho(E)={L}
P
rof
.
 Y
a
nd
re
 M
ald
o
n
ad
o
 
-37
Forma Normal de Chomsky
�Exemplo:
1) L → (S) | ( )
2) S → SE | a | (S) | ( )
3) E → a | (S) | ( )
1) L → C(SC) | C(C)
2) S → SE | a | C(SC) | C(C)
3) E → a | C(SC) | C(C)
4) C(→ (
5) C)→ )
Substituindo os terminais 
por variáveis nas regras cujo 
lado direito é maior ou igual 
a 2:
P
rof
.
 Y
a
nd
re
 M
ald
o
n
ad
o
 
-38
“Quebrando” as regras 
com lado direito maior 
que 2, obtem-se:
Forma Normal de Chomsky
�Exemplo:
1) L → C(SC) | C(C)
2) S → SE | a | C(SC) | C(C)
3) E → a | C(SC) | C(C)
4) C(→ (
5) C)→ )
1) L → C(D1 | C(C)
2) S → SE | a | C(D1 | C(C)
3) E → a | C(D1 | C(C)
4) C(→ (
5) C)→ )
6) D1 → SC)
P
rof
.
 Y
a
nd
re
 M
ald
o
n
ad
o
 
-39
Forma Normal de Chomsky
� Exercício:
� Coloque a seguinte gramática na FNC:
G=(V, T, P, S), onde:
V={S, A, B, C}
T={a, b, c}
P={ S → ASCA
S → ABCA
A → a
B → bBb
B → λ
C → c }
P
rof
.Y
a
nd
re
 M
ald
o
n
ad
o
 
-40
Forma Normal de Greibach
� Uma GLC G = (V, T, P, S) é dita estar 
na Forma Normal de Greibach (FNG) 
se todas as suas regras são da forma:
� A → aα
Sendo A ∈ V, a ∈ T e α ∈ (V∪T)*
� Greibach???
Sheila Greibach, 1939
A maioria dos autores definem α ∈ V*, 
o fato é que a transformação daquela 
forma para esta, mais restritiva, é
trivial.
P
rof
.
 Y
a
nd
re
 M
ald
o
n
ad
o
 
-41
Forma Normal de Greibach
� Depois de simplificada, a transformação de 
uma GLC para FNG envolve as etapas que 
serão descritas na seqüência:
� Etapa 1: renomeação das variáveis para 
uma ordem crescente qualquer;
• As variáveis da gramática são renomeadas em 
uma ordem crescente qualquer;
• Exemplo: A1, A2, … An onde n é um cardinal de 
V;
• Diferentes critérios de renomeação podem 
resultar em diferentes gramáticas na FNG;
P
rof
.
 Y
a
nd
re
 M
ald
o
n
ad
o
 
-42
Forma Normal de Greibach
� Nesta etapa, a partir de uma gramática 
G1=(V1, T1, P1, S), obtêm-se a gramática G2
conforme descrito a seguir:
Gramática resultante: G2 = (V2, T1, P2, S)
Suponha que o cardinal de V1 é n
Construção de V2 e P2
V2 = { A1, A2, …, An } é V1 renomeando os elementos em uma
ordem qualquer
Inicialmente, P2 é P1 renomeando as variáveis na produção
P
rof
.
 Y
a
nd
re
 M
ald
o
n
ad
o
 
-43
Forma Normal de Greibach
� Exemplo:
1) S → AA
2) S → a
3) A → b
4) A → SS
Renomeando as 
variáveis S e A 
para A1 e A2
respectivamente
1) A1→ A2A2
2) A1→ a
3) A2→ b
4) A2→ A1A1
* Note que a gramática já está simplificada.
P
rof
.
 Y
a
nd
re
 M
ald
o
n
ad
o
 
-44
Forma Normal de Greibach
� Etapa 2: transformação das produções para 
a forma Ar→ Asα onde r ≤ s;
• Produções são modificadas garantindo que a 
primeira variável do lado direito é maior ou igual 
que a do lado esquerdo;
• Ar→ Asα onde r > s são modificadas;
• Substitui a variável As pelas suas respectivas 
produções;
• O conjunto de variáveis é finito: existe um limite 
para as produções crescentes;
P
rof
.
 Y
a
nd
re
 M
ald
o
n
ad
o
 
-45
Forma Normal de Greibach
� Exemplo:
1) A1→ A2A2
2) A1→ a
3) A2→ b
4) A2→ A1A1
Substituindo A1
no lado direito 
da regra
1) A1→ A2A2
2) A1→ a
3) A2→ b
4) A2→ aA1
5) A2→ A2A2A1
P
rof
.
 Y
a
nd
re
 M
ald
o
n
ad
o
 
-46
Forma Normal de Greibach
� Etapa 3: exclusão das recursões da 
forma Ar→Arα;
• Podem existir originalmente na gramática 
ou serem geradas pela etapa anterior;
• Eliminação da recursão à esquerda: 
introduzindo variáveis auxiliares e 
incluindo recursão à direita (Br→αBr);
P
rof
.
 Y
a
nd
re
 M
ald
o
n
ad
o
 
-47
Forma Normal de Greibach
� Exemplo:
1) A1→ A2A2
2) A1→ a
3) A2→ b
4) A2→ aA1
5) A2→ A2A2A1
Introduzindo uma 
variável B2 e incluindo 
recursão a direita
1) A1→ A2A2
2) A1→ a
3) A2→ b
4) A2→ aA1
5) A2→ bB2
6) A2→ aA1B2
8) B2→ A2A1
9) B2→ A2A1B2
P
rof
.
 Y
a
nd
re
 M
ald
o
n
ad
o
 
-48
Forma Normal de Greibach
� Etapa 4: garante que o lado direito das 
produções iniciem com um terminal;
• Todas as produções da forma Ar→Asα onde r<s;
• Consequentemente, as produções da maior 
variável An só podem iniciar por terminais no lado 
direito;
• Assim, se em An-1→Anα for substituído An pelas 
suas correspondentes produções (ex: An→aβ), o 
lado direito das produções de An-1 também iniciará
por terminal (ex: An-1→aβα);
• A repetição do algoritmo para An-2, …, A1 resultará
em produções exclusivamente da forma Ar→aα;
P
rof
.
 Y
a
nd
re
 M
ald
o
n
ad
o
 
-49
Forma Normal de Greibach
� Exemplo:
1) A1→ A2A2
2) A1→ a
3) A2→ b
4) A2→ aA1
5) A2→ bB2
6) A2→ aA1B2
8) B2→ A2A1
9) B2→ A2A1B2
A1→ bA2
A1→ aA1A2
A1→ bB2A2
A1→ aA1B2A2
A1→ a
A2→ b
A2→ aA1
A2→ bB2
A2→ aA1B2
B2→ bA1
B2→ aA1A1
B2→ bB2A1
B2→ aA1B2A1
B2→ bA1B2
B2→ aA1A1B2
B2→ bB2A1B2
B2→ aA1B2A1B2
1)
2)
3)
4)
5)
6)
7)
8)
9)
10)
11)
12)
13)
14)
15)
16)
17)
Substituindo as 
variáveis no 
início dos lados 
direitos
P
rof
.
 Y
a
nd
re
 M
ald
o
n
ad
o
 
-50
Forma Normal de Greibach
� Algoritmo das etapas 2 e 3:
Gramática resultante G3 = (V3, T1, P3, S)
Suponha que o cardinal de V2 é n
P3 = P2
para r variando de 1 até n
faça
para s variando de 1 até r-1
faça para toda Ar→ Asα ∈ P3
faça excluir Ar→ Asα de P3;
para toda As→β ∈ P3
faça P3 = P3 ∪ { Ar→βα}
para toda Ar→ Arα ∈ P3
faça excluir Ar→ Arα de P3;
V3 = V3 ∪ {Br}
P3 = P3 ∪ {Br→ α}∪ {Br→ αBr}
para toda Ar→Φ∈ P3 tqΦ não inicia por Ar e 
alguma Ar→ Arα foi excluída
faça P3 = P3 ∪ { Ar→ΦBr};
Garante variável 
da esquerda 
menor ou igual a 
da direita
Elimina recursão 
a esquerda
P
rof
.
 Y
a
nd
re
 M
ald
o
n
ad
o
 
-51
Forma Normal de Greibach
� Algoritmo da etapa 4:
Gramática resultante G4 = (V3, T1, P4, S)
Construção de P4
P4 = P3;
para r variando de n-1 até 1 e toda Ar→ Asα ∈ P4
faça excluir Ar→ Asα de P4 ;
para toda As→ β de P4
faça P4 = P4 ∪ {Ar→ βα};
para toda Br→ Asβr
faça excluir Br→ Asβr de P4
para toda As→ aα
faça P4 = P4 ∪ { Br→ aαβr};
Também é necessário garantir
que as produções relativas às
variáveis auxiliares Br iniciam
por um terminal do lado direito.
P
rof
.
 Y
a
nd
re
 M
ald
o
n
ad
o
 
-52
Forma Normal de Greibach
� Exercício: transforme a seguinte GLC 
para FNG;
S → AB | SCB | SB | bB | b
A → aA | a | cC | c
B → bB | b
C → cC | c
A1→ A2 A3 | A1A4A3 | A1A3 | bA3 | b
A2→ aA2 | a | cA4 | c
A3→ bA3 | b
A4→ cA4 | c
Renomeando as 
variáveis (Etapa 1)
A produções já estão 
na forma Ar→ Asα
onde r ≤ s (Etapa 2)
P
rof
.
 Y
a
nd
re
 M
ald
o
n
ad
o
 
-53
Forma Normal de Greibach
� Exercício (continuação):
A1→ A2A3 | bA3 | b | A2A3B1 | bA3B1 | bB1
A2→ aA2 | a | cA4 | c
A3→ bA3 | b
A4→ cA4 | c
B1→ A4A3 | A3 | A4A3B1 | A3B1
A1→ A2 A3 | A1A4A3 | A1A3 | bA3 | b
A2→ aA2 | a | cA4 | c
A3→ bA3 | b
A4→ cA4 | c Eliminando recursão a 
esquerda: Ar→ Arα(Etapa 3)
P
rof
.
 Y
a
nd
re
 M
ald
o
n
ad
o
 
-54
Forma Normal de Greibach
� Exercício (continuação):
A1→ aA2A3 | aA3 | cA4A3 | cA3 | bA3 | b | aA2A3B1 | aA3B1 | cA4A3B1 | cA3B1 | 
bA3B1 | bB1
A2→ aA2 | a | cA4 | c
A3→ bA3 | b
A4→ cA4 | c
B1→ cA4 A3 | cA3 | bA3 | b | cA4 A3B1 | cA3B1 | bA3B1 | bB1
A1→ A2A3 | bA3 | b | A2A3B1 | bA3B1 | bB1
A2→ aA2 | a | cA4 | c
A3→ bA3 | b
A4→ cA4 | c
B1→ A4A3 | A3 | A4A3B1 | A3B1
Garantindo que todo 
lado direito inicie com 
terminal (Etapa 4)
P
rof
.
 Y
a
nd
re
 M
ald
o
n
ad
o
 
-55
Bibliografia
� MENEZES, Paulo Blauth. Linguagens 
Formais e Autômatos. Porto Alegre: Editora 
Sagra-Luzzatto, 1998;
� DELAMARO, Márcio Eduardo. Linguagens 
Formais e Autômatos. UEM, 1998;
� VIEIRA, Newton José. Introdução aos 
Fundamentos da Computação. São Paulo: 
Editora Thomson Learning, 2006.