Search code examples
context-free-grammarchomsky-normal-form

How to remove this unit production while converting cfg to cnf

In the grammar I have a rule "D → bD | D". How do I remove unit production from this rule for converting it to cnf?

The grammar is this:

S → DBC | Ba 
B → 0B1 | 01 | 𝜀
C → aCb | aC | Bb 
D → bD | D
Solution

  • The production D → D does not contribute anything to the grammar, so you can just delete it. Moreover, the nonterminal D is useless because it cannot derive any sentence; it has no non-recursive production.

    Before removing unit productions, you should first reduce your grammar by removing unproductive and unreachable productions.