Consider the following grammar: πβ0π΄β£0π΅π΅ π΄β00π΄β£π π΅β1π΅β£11πΆ πΆβπ΅β¦
2019
Consider the following grammar:
πβ0π΄β£0π΅π΅π΄β00π΄β£ππ΅β1π΅β£11πΆ πΆβπ΅
Which language does this grammar generate?
- A.
\(L((00)^*0+(11)^*1)\) - B.
\(L(0(11)^*+1(00)^*)\) - C.
\(L((00)^*0)\) - D.
\(L(0(11)^*1)\)
Attempted by 108 students.
Show answer & explanation
Correct answer: C
Answer: The grammar generates the language of strings consisting only of zeros with odd length, i.e., 0(00)* (same as (00)*0).
Reasoning:
Nonterminal A generates (00)* because of the rules A β 00A | Ξ» (zero or more repetitions of "00").
From S β 0A, we get strings of the form 0(00)* (a single 0 followed by zero or more "00" pairs).
The alternative S β 0BB is nonproductive: B β 1B | 11C and C β B cause B and C to recurse without ever producing terminal symbols, so no terminal string can be derived from this branch.
Therefore, the only terminal strings come from S β 0A, so the language is exactly 0(00)*.
Example strings in the language:
0 (one zero)
000 (three zeros)
00000 (five zeros)
A video solution is available for this question β log in and enroll to watch it.