<p>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.</p>

CC BY-SA 2.5
2010-11-28T12:50:32.217Z
Ah, thanks :-). That was really helpful and clarifying for my problem.
plc
CC BY-SA 2.5
2010-11-28T02:34:41.987Z
2010-11-28T02:34:41.987Z
Shiva Kintali
<p>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.</p>

<p>e.g. is this permitted:</p>

<p>$A \to BB$
</p>

<p>or must one do something like</p>

<p>$A \to B_1 B_2$
</p>

<p>$B_1 \to B$
</p>

<p>$B_2 \to B$
</p>

<p>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$</p>

<automata-theory><fl.formal-languages><grammars>
Are variables in RHS of Chomsky Normal Form productions distinct?
plc
# Are variables in RHS of Chomsky Normal Form productions distinct?

(Asked by: username_0 on 2010-11-27)

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$

**Tags:** automata-theory, fl.formal-languages, grammars

---

## 1 answers

### Answer by username_1 on 2010-11-28. Score: 6 | Accepted 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.

> **Comments:**
> **username_0**: Ah, thanks :-). That was really helpful and clarifying for my problem.  

---

