1
$\begingroup$

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*}$$

$\endgroup$
0
$\begingroup$

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.

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

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.