# CNF: Recursion in CFG

How can I deal with recursive terminals in CFG when converting it to CNF? For example,

S -> MN

M -> AM | A

N -> BN | B

A -> a

B -> b

How can I reduce terminals M and N?

• Recall that $A\to\alpha|\beta$ is shorthand for the two productions $A\to\alpha$ and $A\to\beta$. – András Salamon May 23 '13 at 9:17

In your example the problem is in the so-called chain productions $M\to A$ and $N\to B$. Just look how these single nonterminals can finally be rewritten into terminals: $M \Rightarrow A \rightarrow a$. Remove the $M\to A$ chain production and replace it by $M\to a$.
In general, if we have any sequence of nonterminals $X_1 \Rightarrow X_2 \Rightarrow \dots X_n \Rightarrow c$ add the production $X_1\to c$. Then remove the chain productions of the grammar.
Recursion in general is not a problem. It is the essence of context-free grammars! The only requirement of Chomsky Normal Form is that productions are of the form $A \to BC$ and $A\to a$ with $A,B,C$ nonterminals (=variables) and $a$ terminal (letters).
• Sorry, what do you mean by chained $a$'s? – Hendrik Jan May 23 '13 at 0:05
• The recursion is elsewhere: $M\Rightarrow AM \Rightarrow AAM \dots$. To each of these $A$'s you can still apply the $A\to a$ production. Only the single $A$ generated in $M\Rightarrow A \Rightarrow a$ gets now a shortcut $M\to a$. – Hendrik Jan May 23 '13 at 0:11