The reduced grammar equivalent to the grammar, whose production rules are…
2022
The reduced grammar equivalent to the grammar, whose production rules are given below, is
S→AB∣CA
B→BC∣AB
A→a
C→aB∣b
- A.
S→CA,A→a,C→b
- B.
S→CA|B,B→BC|B,A→a,C→aB∣b
- C.
S→CA|B,B→BC,A→a,C→aB|b
- D.
S→AB|AC,B→BC|BA,A→a,C→aB∣b
Attempted by 20 students.
Show answer & explanation
Correct answer: A
Answer: S → CA, A → a, C → b
Reason: identify and remove non-generating symbols, then remove any productions that reference them.
A is generating because A → a produces a terminal string.
B is non-generating because its productions B → BC and B → AB both contain B, so there is no way to derive a string of terminals from B.
Remove B and every production that mentions B. For C, drop C → aB (it references B) but keep C → b.
After removal, the remaining productions are exactly S → CA, A → a, C → b.
Derivation example: S → CA → C A → b a, so the grammar can generate "ba" using the reduced rules.
A video solution is available for this question — log in and enroll to watch it.