3
$\begingroup$

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$

$\endgroup$
6
$\begingroup$

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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.