PadhaikoAll subjects

Past exam question: 2082 Kartik (Back), Q3(c)(ii)

Theory of Computation · 4 marks

Open in the Padhaiko app

Topic: Simplification of CFG; CNF, GNF & BNF

Question

Convert the following CFG into CNF. consists of:

and is the start symbol.

Solution

Elimination of Epsilon Productions: A grammar is in Chomsky Normal Form (CNF) if every rule is of the form (two non-terminals) or (single terminal).

  1. Identify nullable variables: Variable is nullable. is not nullable. For , since is non-nullable, cannot derive .
  2. Replace occurrences of nullable :

Elimination of Unit Productions and Useless Symbols: Eliminating Unit Productions:

Eliminating Useless Symbols:

Conversion into Chomsky Normal Form: Introduce non-terminals for terminals appearing in composite rules:

Transform each production to binary non-terminal form or single terminal:

  1. For :
    • (already CNF)
  2. For :
    • with
  3. For :
    • (already CNF)
    • (already CNF)
    • with

Final CNF Grammar:

Answer:

After eliminating -production and unit production , introducing helper variables converts all productions into standard CNF ( or ).

All past exam questions for Theory of Computation