Theory Of Computation (2160704)

Chomsky Normal Form (CNF)

• A context free grammar is in Chomsky normal form (CNF) if every production is one of these two forms:
  1. A -> BC
  2. A -> α
  Where A, B, and C are nonterminal and α is terminal.

Convert CFG To CNF

• S -> ASA | aB,
• A -> B | S,
• B -> b | e

1. Elimination of ^ production
   • There is no ^ Production In The Given CFG
2. Eliminate Unit Production
   • S -> ASA | aB,
   • A -> b | e | ASA | aB,
   • B -> b | e
3. Replace all mixed string with solid NT
   • S -> ASA | P
   • A -> b | e | ASA | P
   • B -> b | e
   • P -> aB
4. Shorten the string of NT to length 2
   • S -> AX₁
   • X₁ -> SA
   • A -> b | e | AX1 | P
   • B -> b | e
   • P -> aB