PadhaikoAll subjects

Past exam question: 2081 Chaitra (Regular), Q3(b)

Theory of Computation · 5 marks

Open in the Padhaiko app

Topic: Simplification of CFG; CNF, GNF & BNF

Question

Convert the following CFG, into CNF: where , , and is starting symbol.

Solution

Elimination of Epsilon Productions: Given grammar rules:

  1. Identify Nullable Variables:
    • is nullable.
    • is nullable.
    • is nullable. Since start symbol is nullable, we introduce a new start symbol .
  2. Eliminate from and :
    • From : when , we obtain . So .
    • From : when , we obtain . So .
    • From : remains .
    • New start symbol productions: .

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

Eliminating Useless Symbols:

Conversion into Chomsky Normal Form: Introduce non-terminals for terminal symbols:

Convert rules of length into binary non-terminal form:

  1. For :
    • with
  2. For :
    • with
  3. For :

Final CNF Grammar:

Answer:

Eliminating -productions gives and , removing unit productions gives (after which is unreachable and is dropped), and introducing variables produces the final grammar in Chomsky Normal Form.

All past exam questions for Theory of Computation