I am trying to do an exercise where I translate a grammar into Chomsky normal form. I understand how to do this in normal circumstances but this time the grammar I am working with is right recursive. (Technically the grammar is the answer to the previous question, so I might just have the wrong gamma.)
I think I can do this by using a fixed sequence of rules in place of ε rules but I want to make sure I'm not heading in the wrong direction. It's easier to explain with an example:
For a grammar that produces n 'a's where n is greater than 0 and a multiple of three: (don't worry, this is entirely different to the grammar my actual exercise)
S-> Aaaa
A-> Aaaa
A-> ε
Would the correct Translation be:
S0-> S
S-> A'B
A'-> AA'
A-> A'B
B-> B'C
A'-> a
B'-> a
C-> a
Although your grammar is right-recursive, you can perform the Chomsky Normal Form transformation as you would any other (non-right recursive) grammar. Simply follow the algorithm outlined in your book, which probably consists of two steps: (1) replace all occurrences of terminals a by rules A -> a, where A does not occur in the rule set; (2) transform all rules A -> w, where len(w) > 2, by rules of length 2 containing fresh variables.
For your A rule, then, construct a rule for deriving terminals, say K -> a, and replace all occurrences of the terminal a:
A -> AKKK
Then put the grammar into CNF
A -> AA'
A' -> KA''
A'' -> KK