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?

  • $\begingroup$ Recall that $A\to\alpha|\beta$ is shorthand for the two productions $A\to\alpha$ and $A\to\beta$. $\endgroup$ – 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).

  • $\begingroup$ if i change it to M -> a, won't it no longer accept chained a's? $\endgroup$ – Kudayar Pirimbaev May 23 '13 at 0:03
  • $\begingroup$ Sorry, what do you mean by chained $a$'s? $\endgroup$ – Hendrik Jan May 23 '13 at 0:05
  • $\begingroup$ 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? $\endgroup$ – Kudayar Pirimbaev May 23 '13 at 0:07
  • $\begingroup$ 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$. $\endgroup$ – Hendrik Jan May 23 '13 at 0:11
  • $\begingroup$ so recursion satisfies chomsky-normal form, am i right? $\endgroup$ – Kudayar Pirimbaev May 23 '13 at 0:15

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.