Upload
leandra-buchanan
View
44
Download
0
Embed Size (px)
DESCRIPTION
Formas Normais de Gramáticas Livres de Contexto. Forma Normal de Chomsky. Todas as produções têm a forma:. e. variável. variável. terminal. Exemplos :. Forma Normal de Chomsky. Não Forma Normal de Chomsky. Conversão para Forma Normal de Chomsky. Exemplo :. Não Forma Normal - PowerPoint PPT Presentation
Citation preview
6
Introduza variável intermediária:
cT
bT
aT
ATB
TTTA
ABTS
c
b
a
c
baa
a
cT
bT
aT
ATB
TTTA
BTV
AVS
c
b
a
c
baa
a
1
1
1V
7
Introduza variável intermediária:
cT
bT
aT
ATB
TTV
VTA
BTV
AVS
c
b
a
c
ba
a
a
2
2
1
1
2V
cT
bT
aT
ATB
TTTA
BTV
AVS
c
b
a
c
baa
a
1
1
8
Gramática Final na Forma Normal de Chomsky:
cT
bT
aT
ATB
TTV
VTA
BTV
AVS
c
b
a
c
ba
a
a
2
2
1
1
AcB
aabA
ABaS
Gramática inicial
9
De qualquer gramática livre de contextoque não esteja na Forma Normal de Chomsky
podemos obter: Uma gramática equivalente na Forma Normal de Chomsky
Em geral:
11
Para cada símbolo : a
Nas produções: substitua por a aT
Adicione a produção aTa
Nova variável: aT
12
Substitua toda produção nCCCA 21
por
nnn CCV
VCV
VCA
12
221
11
Novas variáveis intermediárias:
221 ,,, nVVV
13
Teorema:
Para toda gramática livre de contextoexiste uma gramática equivalentena Forma Normal de Chomsky
14
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
17
aaS
abSbS
Conversão para a Forma Normal de Greinbach:
bT
aT
aTS
STaTS
b
a
a
bb
Forma Normalde Greinbach
18
Teorema:
Para qualquer gramática livre de contextoexiste uma gramática equivalentena Forma Normal de Greinbach
19
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
21
O Algoritmo CYK
Entrada:
• Gramática na Forma Normal de ChomskyG
• String
Saída:
ou não )(GLw
w
se
27
Portanto: )(GLaabbb
Complexidade deTempo :3||w
O algoritmo CYK pode ser facilmente convertido em um parser
Observação:
47
Um string é aceito se:
• Toda a entrada é consumida
• O último estado é um estado final
Neste exemplo, a pilha está vazia no final.
50
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.