Solution

The correct answer is option 2: B only

Key Points

A grammar is said to be in Chomsky Normal Form (CNF) if:

• Every production rule is of the form: A → BC or A → a
• A, B, C are variables (non-terminals) and a is a terminal
• B and C must not be the start symbol
• No productions with >2 non-terminals are allowed

Analysis of each CFG:

• A.
  • S → ABC → invalid (CNF allows max 2 non-terminals)
  • S → AB → valid CNF
  • A → a, B → b, C → d → valid (single terminals)
  • ❌ Not in CNF (due to S→ABC)
• B.
  • X → RT / TR → valid (2 variables)
  • T → t → valid (terminal)
  • R → XT → valid (2 variables)
  • R → r → valid (terminal)
  • ✅ Fully CNF compliant
• C.
  • P → qP / sQ → invalid (terminal+non-terminal)
  • Q → r / s → valid but irrelevant
  • ❌ Not in CNF
• D.
  • M → MN / MP → valid
  • N → nm → invalid (two terminals)
  • N → n → valid
  • P → P → invalid (unit production)
  • ❌ Not in CNF

Explanation of options:

• Option 1 – A & B only: ❌ Incorrect (A violates CNF)
• Option 2 – B only: ✅ Correct
• Option 3 – C only: ❌ Incorrect
• Option 4 – B & D only: ❌ Incorrect (D violates CNF)

Hence, the correct answer is: option 2: B only