Reusing variable in converting grammar to Chomsky Normal Form I'm not sure if reusing variable is allowed in CNF.


For example, I have this grammar not in CNF. So I have to convert it to CNF.

1. S-&gt;abAB|abB|abA|ab
2. A-&gt;bAa|ba
3. B-&gt;BAa|bAa|ba|Ba|Aa|a


For conversion, I'm using a convention where new variables and terminals are in the form

(V1,V2,V3,...,Vk) for k &gt; 0
Ti where i are terminals (a,b,c,...,z)


Introduce new terminals for each terminal in the grammar
S-&gt;(Ta)(Tb)AB|(Ta)(Tb)B|(Ta)(Tb)A|(Ta)(Tb)
A-&gt;(Tb)A(Ta)|(Tb)(Ta)
B-&gt;BA(Ta)|(Tb)A(Ta)|(Tb)(Ta)|B(Ta)|A(Ta)|a
Ta-&gt;a
Tb-&gt;b


For the purpose of my question, I'm only focusing only on B productions due to the repetition of A(Ta).

...
B-&gt;BV1|(Tb)V2|(Tb)(Ta)|B(Ta)|A(Ta)|a
V1-&gt;A(Ta)
V2-&gt;A(Ta)
...


See V1 and V2, they have the same right-hand side that is A(Ta).
"Chomsky normal form" is something a grammar is, rather than the specific procedure used to make it. So nothing prevents you from reusing a symbol like that; the grammar will still be CNF if you do.