Discussion
Consider the context-free grammar \(G\) below
\(S \to aSb \mid X\)
\(X \to aX \mid Xb \mid a \mid b\),
where \(S\) and \(X\) are non-terminals, and \(a\) and \(b\) are terminal symbols. The starting non-terminal is \(S\).
Which one of the following statements is CORRECT?
Answer: B
The language is \(a^{*}(a+b)b^{*}\).
Start with X. The rules X \(\to\) aX and X \(\to\) Xb add any number of a's on the left and b's on the right, and the derivation ends with a single a or b in the middle. So X generates \(a^{*}(a+b)b^{*}\): some a's, then one a or b, then some b's.
S \(\to\) aSb wraps that in n further a's and n further b's, giving \(a^{n}a^{*}(a+b)b^{*}b^{n}\), which is still \(a^{*}(a+b)b^{*}\). The matching counts add nothing, because X can already produce any numbers of a's and b's on its own.
\((a+b)^{*}\) includes the empty string and strings like ba, which G cannot produce, since every b comes after every a. \(a^{*}b^{*}(a+b)\) contains bba, which G cannot generate. And since the language is given by a regular expression, it is regular.
Post your comment
Please log in or register to post a comment.
Examination Categories
- SSC Exams
- Banking Exams
- Teaching Exams
- Civil Services Exams
- Railways Exams
- Engineering Recruitment Exams
- Defence Exams
- State Government Exams
- Police Exams
- Insurance Exams
- Nursing Exams
- Other Government Exams
- NRA CET
- PG Entrance Exams
- Campus Placement
- MBA Entrance Exams
- CUET and UG Entrance
- Judiciary Exams
- Regulatory Body Exams
- Software Development