# Are variables in RHS of Chomsky Normal Form productions distinct?

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$

## 1 Answer

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.

• Ah, thanks :-). That was really helpful and clarifying for my problem. – plc Nov 28 '10 at 12:50