I'm wondering if it is permitted for production rules in a context-free grammar (CFG) in Chomsky Normal Form (CNF) to have multiple occurences of the same variable in the right-hand side of the productions.e.g. is this permitted:$A \to BB$ or must one do something like$A \to B_1 B_2$ $B_1 \to B$ $B_2 \to B$ The only definitions of CNF I have found define production rules of the form $A \to B C$ , but none ever state that $B \neq C$
Are variables in RHS of Chomsky Normal Form productions distinct?
automata theory;fl.formal languages;grammars
Yes. The production rules of the form $A \rightarrow BB$ are allowed. One of the motivations behind CNF is to make the parse tree a binary tree so that we can have a unified way of talking about the relationship between the depth of the parse tree and the length of its yield. So having rules of the form $A \rightarrow BB$ does not disrupt this goal. However, replacing $A \rightarrow BB$ by $A \rightarrow B_1B_2$, $B_1 \rightarrow B$ and $B_2 \rightarrow B$ might create problems in analyzing the depth of parse tree especially when you have rules like $B \rightarrow XY$. This will create intermediate nodes in the parse tree with outdegree one, while the goal of CNF is to push such nodes to the leaves.