A tradução de um direito recursiva gramática na Forma Normal de Chomsky

Question

Eu estou tentando fazer um exercício onde eu traduzir uma gramática na forma normal de Chomsky.Sei como fazer isso, em circunstâncias normais, mas desta vez a gramática eu estou trabalhando com o é direito recursiva.(Tecnicamente, a gramática é a resposta para a pergunta anterior, então eu só poderia ter errado gama.)

Eu acho que pode fazer isso usando uma seqüência fixa de regras em lugar de ε regras, mas eu quero ter certeza que eu não estou indo na direção errada.É mais fácil explicar com um exemplo:

Para uma gramática que produz n 'a onde n é maior que 0 e um múltiplo de três:(não se preocupe, este é totalmente diferente da gramática do meu exercício real)

S-> Aaaa
A-> Aaaa
A-> ε

Seria a Tradução correta será:

S0-> S
S-> A'B
A'-> AA'
A-> A'B
B-> B'C
A'-> a
B'-> a
C-> a

Answer 1

Apesar de sua gramática é direito-recursiva, você pode executar a Forma Normal de Chomsky transformação, como você faria com qualquer outro (não-direito recursiva) gramática.Basta seguir o algoritmo descrito em seu livro, que provavelmente consiste de duas etapas:(1) substitua todas as ocorrências de terminais um regras Um -> um, onde Um não ocorre no conjunto de regras;(2) transformar todas as regras Um -> w, onde len(w) > 2, por meio de regras de comprimento 2 que contém os variáveis.

Para a sua Um a regra, então, construir uma regra para derivar terminais, dizer K -> um, e substituir todas as ocorrências do terminal um:

A -> AKKK

Em seguida, coloque a gramática em CNF

A    -> AA'
A'   -> KA''
A''  -> KK