·

Ciência da Computação ·

Outros

Send your question to AI and receive an answer instantly

Ask Question

Preview text

Linguagens Formais Tema 6 Forma Normal de Greibach REFORÇANDO A APRENDIZAGEM PONTOS PRINCIPAIS Forma Normal de Greibach Fundamentos Uma gramática livredocontexto está na forma normal de Greibach se toda regra é da forma A aα onde A é uma variável a é um terminal e α é uma palavra de variáveis Forma Normal de Greibach Conversão de uma GLC FNG Para que o algoritmo funcione é necessário que a gramática esteja na Forma Normal de Chomsky Depois deste requisito satisfeito temse os seguintes passos 1 Renomeação das variáveis em uma ordem crescente qualquer 2 Transformação de produções para a forma Ar Asα onde r s e exclusão das recursões da forma Ar Arα 3 Um terminal no início do lado direito de cada produção 4 Produções na forma A aα onde α é composta por variáveis Forma Normal de Greibach Exemplo dada a GLC converter para FNG S AB SCB A aA C B bB b C cC ε Forma Normal de Greibach Eliminação de produções vazias V λ A C S AB SCB SB B A aA C a B bB b C cC c Forma Normal de Greibach Eliminação de produções unitárias FechoS B FechoA C FechoB FechoC S AB SCB SB bB b A aA a cC c B bB b C cC c Não existem símbolos inúteis Forma Normal de Greibach Transformação para FNG Etapa 1 Renomeando as variáveis A1 A2A3 A1A4A3 A1A3 bA3 b A2 aA2 a cA4 c A3 bA3 b A4 cA4 c Forma Normal de Greibach Transformação para FNG Etapas 2 e 3 Eliminando Ar As com s r e recursão à esquerda A1 A2A3 bA3 b A2A3B1 bA3B1 bB1 A2 aA2 a cA4 c A3 bA3 b A4 cA4 c B1 A4A3 A4A3B1 A3 A3B1 Eliminar Recursividade à Esquerda Regras do tipo A Aα β Vão ficar A β B β B α B α Forma Normal de Greibach Transformação para FNG Etapa 4 Garantindo que o lado esquerdo comece com um terminal A1 aA2A3 aA3 cA4A3 cA3 subs A2 bA3 b aA2A3B1 aA3B1 cA4A3B1 cA3B1 subs A2 bA3B1 bB1 A2 aA2 a cA4 c A3 bA3 b A4 cA4 c B1 cA4A3 cA3 subs A4 cA4A3B1 cA3B1 subs A4 bA3 b subs A3 bA3B1 bB1 subs A3 Forma Normal de Greibach Exercicios de Fixacao Faça a conversão da GLC para FNG S aAd A A Bc ε B Ac a