Upload
lyduong
View
234
Download
0
Embed Size (px)
Citation preview
InformáticaPUC-RioINF1626 Linguagens Formais e Autômatos (2013-2)
©Clarisse S. de Souza, 2013 1
Linguagens Formais e Autômatos (LFA)
Aula de 23/10/2013
Linguagens Livres de Contexto: Formas Normais e Propriedades Formais
©Clarisse S. de Souza, 2013 1
InformáticaPUC-RioINF1626 Linguagens Formais e Autômatos (2013-2)
Formas Normais
Brevemente descritas na aula anterior
O que são?Para que servem?
©Clarisse S. de Souza, 2013 2
InformáticaPUC-RioINF1626 Linguagens Formais e Autômatos (2013-2)
©Clarisse S. de Souza, 2013 3
InformáticaPUC-RioINF1626 Linguagens Formais e Autômatos (2013-2)
©Clarisse S. de Souza, 2013 4
InformáticaPUC-RioINF1626 Linguagens Formais e Autômatos (2013-2)
©Clarisse S. de Souza, 2013 5
InformáticaPUC-RioINF1626 Linguagens Formais e Autômatos (2013-2)
©Clarisse S. de Souza, 2013 6
InformáticaPUC-RioINF1626 Linguagens Formais e Autômatos (2013-2)
©Clarisse S. de Souza, 2013 7
Slide Corrigido
©Clarisse S. de Souza, 2013 8
InformáticaPUC-RioINF1626 Linguagens Formais e Autômatos (2013-2)
Método de Normalização para FNC (Ramos,2009)1. P ’ ;2. N ‘ N;3. Se ABC P, com A,B,C N, então ABC P ‘;4. Se A P, com A N, , então A P ‘;5. Se S P, então S P ‘;6. Para cada produção p P da forma: AX1X2, . . . ,Xn, com n > 2
se Xi , então criam-se novos não-terminais Yi e produções YiXi substituindo-se as ocorrências de Xi por Yi em p. Acrescentam-se os novos não-terminais Yi a N ‘ e as novas produções a P ‘.
7. Para cada produção da forma: AX1X2, . . . ,Xn, com n > 2 e Xi N, 1 i ngerada no passo (6), criar um novo conjunto de não-terminais Zi e de produções da forma:
{A X1Z1,Z1 X2Z2,. . .Zn−2 Xn−1Xn} acrescentando-os, respectivamente, aos conjuntos N ‘ e P ‘.
©Clarisse S. de Souza, 2013 9
InformáticaPUC-RioINF1626 Linguagens Formais e Autômatos (2013-2)
Exercício de Normalização para FNC1. P ’ ;2. N ‘ N;3. Se ABC P, com A,B,C N, então ABC P ‘;4. Se A P, com A N, , então A P ‘;5. Se S P, então S P ‘;6. Para cada produção p P da forma: AX1X2, . . . ,Xn, com n > 2
se Xi , então criam-se novos não-terminais Yi e produções YiXi substituindo-se as ocorrências de Xi por Yi em p. Acrescentam-se os novos não-terminais Yi a N ‘ e as novas produções a P ‘.
7. Para cada produção da forma: AX1X2, . . . ,Xn, com n > 2 e Xi N, 1 i ngerada no passo (6), criar um novo conjunto de não-terminais Zi e de produções da forma:
{A X1Z1,Z1 X2Z2,. . .Zn−2 Xn−1Xn} acrescentando-os, respectivamente, aos conjuntos N ‘ e P ‘.
©Clarisse S. de Souza, 2013 10
Normalize estas produções:
InformáticaPUC-RioINF1626 Linguagens Formais e Autômatos (2013-2)
Exercício de Análise Sintática
Produza a árvore sintática correspondente à expressão a * (a + a) + (a * (a + a)) pela GLC não normalizada e depois pela GLC normalizada.
Aprecie as diferenças.
Que tipo de estratégia de derivação você usou? Usou-a nos dois casos? Poderia ter usado estratégias diferentes para um caso e outro?
©Clarisse S. de Souza, 2013 11
InformáticaPUC-RioINF1626 Linguagens Formais e Autômatos (2013-2)
a*(a+a)+(a*(a+a))
©Clarisse S. de Souza, 2013 12
InformáticaPUC-RioINF1626 Linguagens Formais e Autômatos (2013-2)
Autoaprendizado: Método de Normalização para FNG
Fontes de estudo:• Livro texto da disciplina e/ou• MENEZES, Paulo Blauth. Linguagens Formais e
Autômatos. Porto Alegre: Editora Sagra-Luzzatto. 1998
Ambos estão disponíveis na Biblioteca
©Clarisse S. de Souza, 2013 13