# 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

## 1 Answer

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).

• if i change it to M -> a, won't it no longer accept chained a's? – Kudayar Pirimbaev May 23 '13 at 0:03
• Sorry, what do you mean by chained $a$'s? – Hendrik Jan May 23 '13 at 0:05
• i mean, since M is no longer recursive in M -> a, it would stop at only one a, right? but how can i keep recursive property in non-recursive way? – Kudayar Pirimbaev May 23 '13 at 0:07
• 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
• so recursion satisfies chomsky-normal form, am i right? – Kudayar Pirimbaev May 23 '13 at 0:15