Tradurre un diritto di grammatica ricorsiva in Chomsky forma normale

Question

Sto provando a fare un esercizio in cui mi traduco una grammatica in forma normale di Chomsky. Capisco come fare questo in circostanze normali, ma questa volta la grammatica con cui sto lavorando è ricorsiva destra. (Tecnicamente la grammatica è la risposta alla domanda precedente, quindi potrei avere la gamma sbagliata.)

penso di poter fare questo utilizzando una sequenza fissa di regole al posto di regole ε ma voglio fare in modo che non sto andando nella direzione sbagliata. E 'più facile da spiegare con un esempio:

Per una grammatica che produce n 'a di dove n è maggiore di 0 e un multiplo di tre: (Non ti preoccupare, questo è del tutto diverso alla grammatica mio esercizio effettivo)

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

Può la traduzione corretta sia:

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

Answer 1

Anche se la grammatica è di destra-ricorsiva, è possibile eseguire la trasformazione Chomsky forma normale, come si farebbe con qualsiasi altro grammatica (ricorsiva non a destra). Basta seguire l'algoritmo descritto nel suo libro, che probabilmente si compone di due fasi: (1) sostituire tutte le occorrenze di terminali a da regole A -> a , dove a non si verifica nel set di regole; (2) trasformare tutte le regole A -.> W , dove len (w)> 2, da regole di lunghezza 2 contenente le variabili freschi

Per A regola, quindi, costruire una regola per terminali derivanti, diciamo K -> a , e sostituire tutte le occorrenze del terminale un :

A -> AKKK

Poi ha messo la grammatica in CNF

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