Formas Normais
de
Gramáticas Livres de Contexto
1
Forma Normal de Chomsky
Todas as produções têm a forma:
A  BC
variável
e
variável
Aa
terminal
2
Exemplos:
S  AS
S a
S  AS
S  AAS
A  SA
Ab
A  SA
A  aa
Forma Normal
de Chomsky
Não
Forma Normal
de Chomsky
3
Conversão para
Forma Normal de Chomsky
Exemplo:
S  ABa
A  aab
B  Ac
Não
Forma Normal
de Chomsky
4
Introduza variáveis para terminais: Ta , Tb , Tc
S  ABTa
S  ABa
A  aab
B  Ac
A  TaTaTb
B  ATc
Ta  a
Tb  b
Tc  c
5
Introduza variável intermediária: V1
S  ABTa
A  TaTaTb
B  ATc
Ta  a
Tb  b
Tc  c
S  AV1
V1  BTa
A  TaTaTb
B  ATc
Ta  a
Tb  b
Tc  c
6
Introduza variável intermediária:
S  AV1
V1  BTa
A  TaTaTb
B  ATc
Ta  a
Tb  b
Tc  c
V2
S  AV1
V1  BTa
A  TaV2
V2  TaTb
B  ATc
Ta  a
Tb  b
Tc  c
7
Gramática Final na Forma Normal de Chomsky:
S  AV1
V1  BTa
Gramática inicial
S  ABa
A  aab
B  Ac
A  TaV2
V2  TaTb
B  ATc
Ta  a
Tb  b
Tc  c
8
Em geral:
De qualquer gramática livre de contexto
que não esteja na Forma Normal de Chomsky
podemos obter:
Uma gramática equivalente
na Forma Normal de Chomsky
9
O Procedimento
Primeiro remova:
Variáveis nulas
Produções Unitárias
Variáveis inatingíveis
10
Para cada símbolo
a:
Adicione a produção
Ta  a
Nas produções: substitua
Nova variável:
a por Ta
Ta
11
Substitua toda produção A  C1C2 Cn
por
A  C1V1
V1  C2V2

Vn2  Cn1Cn
Novas variáveis intermediárias:
V1, V2 , ,Vn2
12
Teorema:
Para toda gramática livre de contexto
existe uma gramática equivalente
na Forma Normal de Chomsky
13
Observações
• Formas normais de Chomsky são boas
para parsing e para a prova de teoremas
• É muito fácil encontrar
a Forma Normal de Chomsky
para qualquer gramática livre de contexto
14
Forma Normal de Greinbach
Todas as produções têm a forma:
A  a V1V2 Vk
terminal
k 0
variáveis
15
Exemplos:
S  cAB
A  aA | bB | b
Bb
Forma Normal
de Greinbach
S  abSb
S  aa
Não
Forma Normal
de Greinbach
16
Conversão para a Forma Normal de Greinbach:
S  abSb
S  aa
S  aTb STb
S  aTa
Ta  a
Tb  b
Forma Normal
de Greinbach
17
Teorema:
Para qualquer gramática livre de contexto
existe uma gramática equivalente
na Forma Normal de Greinbach
18
Observações
• Formas normais de Greinbach são muito boas
para parsing
• É difícil obter a Forma Normal de Greinbach
para qualquer gramática livre de contexto
19
Uma Aplicação
de
Forma Normal de Chomsky
20
O Algoritmo CYK
Entrada:
• Gramática G na Forma Normal de Chomsky
• String
w
Saída:
se
w L(G ) ou não
21
Algoritmo CKY
Exemplo de entrada:
• Gramática
G: S  AB
A  BB
Aa
B  AB
Bb
• String
w : aabbb
22
aabbb
a
a
b
b
aa
ab
bb
bb
aab
abb
bbb
aabb
abbb
b
aabbb
23
S  AB
A  BB
Aa
B  AB
Bb
a
A
a
A
b
B
b
B
aa
ab
bb
bb
aab
abb
bbb
aabb
abbb
aabbb
b
B
24
S  AB
A  BB
Aa
B  AB
Bb
a
A
a
A
b
B
b
B
aa
bb
A
bbb
bb
A
aab
ab
S,B
abb
aabb
abbb
aabbb
b
B
25
S  AB
A  BB
Aa
B  AB
Bb
a
A
a
A
b
B
b
B
aa
bb
A
bbb
S,B
bb
A
aab
S,B
ab
S,B
abb
A
aabb
A
abbb
S,B
aabbb
S,B
b
B
26
Portanto:
aabbb  L(G)
Complexidade deTempo :
3
| w|
Observação:
O algoritmo CYK pode ser
facilmente convertido em um parser
27
Autômatos de Pilha
PDAs
28
Autômato de Pilha -- PDA
String de entrada
Pilha
Estados
29
Símbolo Marcador de Fundo de Pilha
Pilha
Pilha
$
z
fundo de pilha
símbolo especial
30
Os Estados
Símbolo
na entrada
Símbolo
desempilhado
Símbolo
empilhado
a,
b
®
c
q1
q2
31
q1
a, b ® c
q2
entrada

a

a


pilha
b
h
e
$
topo
Substitua
c
h
e
$
32
q1
a, l ® c
q2
entrada

a

pilha
b
h
e
$
topo
a

Push

c
b
h
e
$
33
q1
a, b ® l
q2
entrada

a

a


pilha
b
h
e
$
topo
Pop
h
e
$
34
q1
a, l ® l
q2
entrada

a

a


pilha
b
h
e
$
topo
Não Muda
b
h
e
$
35
Não Determinismo
a, b ® c
q2
q1
a, b ® c
q1
q3
l, b ® c
q2
l - transição
36
NPDA: PDA Não Determinista
Exemplo:
a, l ® a
q0
b, a ® l
l, l ® $ q b, a ® l q l, $ ® l q
3
2
1
37
Exemplo de Execução: Instante 0
Entrada
a a a b b b
Pilha
estado
corrente
q0
a, l ® a
b, a ® l
l, l ® $ q b, a ® l q l, $ ® l q
3
2
1
38
Instante 1
Entrada
a a a b b b
$
Pilha
a, l ® a
q0
b, a ® l
l, l ® $ q b, a ® l q l, $ ® l q
3
2
1
39
Instante 2
Entrada
a a a b b b
a
$
Pilha
a, l ® a
q0
b, a ® l
l, l ® $ q b, a ® l q l, $ ® l q
3
2
1
40
Instante 3
Input
a
a
$
a a a b b b
Pilha
a, l ® a
q0
b, a ® l
l, l ® $ q b, a ® l q l, $ ® l q
3
2
1
41
Time 4
Entrada
a a a b b b
a
a
a
$
Pilha
a, l ® a
q0
b, a ® l
l, l ® $ q b, a ® l q l, $ ® l q
3
2
1
42
Instante 5
Entrada
a a a b b b
a
a
a
$
Pilha
a, l ® a
q0
b, a ® l
l, l ® $ q b, a ® l q l, $ ® l q
3
2
1
43
Instante 6
Entrada
a
a
$
a a a b b b
Pilha
a, l ® a
q0
b, a ® l
l, l ® $ q b, a ® l q l, $ ® l q
3
2
1
44
Instante 7
Entrada
a
$
a a a b b b
Pilha
a, l ® a
q0
b, a ® l
l, l ® $ q b, a ® l q l, $ ® l q
3
2
1
45
Instante 8
Entrada
a a a b b b
Pilha
a, l ® a
b, a ® l
aceita
q0
l, l ® $ q b, a ® l q l, $ ® l q
3
2
1
46
Um string é aceito se:
• Toda a entrada é consumida
• O último estado é um estado final
Neste exemplo, a pilha está vazia no final.
47
O string de entrada
é aceito pelo NPDA:
a, l ® a
q0
aaabbb
b, a ® l
l, l ® $ q b, a ® l q l, $ ® l q
3
2
1
48
Em geral,
L  {a b : n  0}
n n
é a linguagem aceita pelo NPDA:
a, l ® a
q0
b, a ® l
l, l ® $ q b, a ® l q l, $ ® l q
3
2
1
49
Autômato de Pilha - convenções
• Adotamos a convenção de que um autômato de pilha
M aceita um string w se algum caminho de
computação de w em M, iniciando no estado inicial,
com a pilha vazia, termina em um estado final
(possivelmente com a pilha vazia).
• Todo autômato começa com a pilha contendo
apenas o marcador de fundo de pilha. Se toda
transição que leva a um estado final desempilha
esse marcador, garante-se que a computação
termina c/ pilha vazia.
50
Outro Exemplo de NPDA
NPDA
M
L( M )  {ww }
R
a,   a
b,   b
q0
a, a  
b, b  
l, l ® l
q1
l, $ ® $ q
2
51
Exemplo de Execução:
Instante 0
Entrada
a b b a
$
a,   a
b,   b
q0
l, l ® l
a, a  
b, b  
q1
Pilha
l, $ ® $ q
2
52
Instante 1
Entrada
a b b a
a,   a
b,   b
q0
l, l ® l
a
$
a, a  
b, b  
q1
Pilha
l, $ ® $ q
2
53
Instante 2
Entrada
b
a
$
a b b a
a,   a
b,   b
q0
l, l ® l
a, a  
b, b  
q1
Pilha
l, $ ® $ q
2
54
Instante 3
Entrada
b
a
$
a b b a
a,   a
b,   b
q0
l, l ® l
a, a  
b, b  
q1
Pilha
l, $ ® $ q
2
55
Instante 4
Entrada
b
a
$
a b b a
a,   a
b,   b
q0
l, l ® l
a, a  
b, b  
q1
Stack
l, $ ® $ q
2
56
Instante 5
Entrada
a b b a
a,   a
b,   b
q0
l, l ® l
a
$
a, a  
b, b  
q1
Pilha
l, $ ® $ q
2
57
Instante 6
Entrada
a b b a
$
a,   a
b,   b
q0
l, l ® l
a, a  
b, b  
Pilha
aceita
q1
l, $ ® l
l, $ ® $ q
2
58