I have a context-free grammar with the following production rules, $S$ being the start symbol:

$$\begin{align*} S &\to AB \\ A &\to a \\ B &\to a\end{align*}$$

Is this in Chomsky normal form?

My problem is I thought CNF is supposed to be an efficient way to write a grammar, yet the grammar is not efficient in the sense that we can clean its rules as follows:

$$\begin{align*}S &\to AA\\ A &\to a\end{align*}$$


1 Answer 1


Both grammars are in CNF. One of the possible rule formats for CNF is $A \to BC$, where $A$, $B$, and $C$ are non-terminals, but it is not necessary for them to be different from another. Hence, in your case, $S \to AA$ is also a valid rule for CNF.

I should add CNF has nothing to do with an "efficient" way to write a grammar (however you should define that; if you simply mean the description is shorter, then counterexamples abound). Rather, CNF is useful when employing techniques such as the CYK algorithm.

  • $\begingroup$ I got confused since many sources speak about removing useless variables before constructing the CNF $\endgroup$
    – PascalIv
    Dec 18, 2018 at 13:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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