Efficiency/Redundancy in Chomsky normal form I have a context-free grammar with the following production rules, $S$ being the start symbol:

$$\begin{align*}
S &amp;\to AB \\
A &amp;\to a \\
B &amp;\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 &amp;\to AA\\
A &amp;\to a\end{align*}$$
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.