Define CNF; convert S→MaN|bL|bM grammar

Chomsky Normal Form

A CFG is in CNF if every production has one of the forms

• A → BC (two variables), or
• A → a (one terminal),

and the start symbol may have S → ε if ε ∈ L (then S must not appear on any right side). Every CFG can be converted to CNF. CNF is used in the CYK parsing algorithm.

Conversion

Grammar: S → MaN | bL | bM; L → ab | cN | M | ε; M → a | cM; N → abN.

Step 1: Useless symbols. N → abN is the only rule for N and always contains N, so N generates no terminal string. Remove N and rules containing it:

S → bL | bM
L → ab | M | ε       (cN removed)
M → a | cM

Step 2: Remove ε. Only L is nullable. S is not nullable, so no ε remains.

S → bL | b | bM
L → ab | M
M → a | cM

Step 3: Remove unit L → M.

S → bL | b | bM
L → ab | a | cM
M → a | cM

Step 4: Convert to CNF. Add Xa → a, Xb → b, Xc → c, replace terminals in long rules:

S  → XbL | b | XbM
L  → XaXb | a | XcM
M  → a | XcM
Xa → a
Xb → b
Xc → c

This is in CNF. (Examples of strings generated: b, ba, bab, bca, bcca.)