Discussion
Consider the following context-free grammars:
\(G_{1}\): \(S \rightarrow aS \mid B\), \(B \rightarrow b \mid bB\)
\(G_{2}\): \(S \rightarrow aA \mid bB\), \(A \rightarrow aA \mid B \mid \varepsilon\), \(B \rightarrow bB \mid \varepsilon\)
Which one of the following pairs of languages is generated by \(G_{1}\) and \(G_{2}\), respectively?
Answer: D
\(G_{1}\) and \(G_{2}\) generate \(\{a^{m}b^{n} \mid m \ge 0 \text{ and } n \gt 0\}\) and \(\{a^{m}b^{n} \mid m \gt 0 \text{ or } n \gt 0\}\).
\(G_{1}\): \(S \rightarrow aS \mid B\) produces any number of a's, possibly none, then switches to \(B\). \(B \rightarrow b \mid bB\) produces one or more b's. So \(m \ge 0\) and \(n \gt 0\).
\(G_{2}\): \(S\) must start with a (then \(A\)) or b (then \(B\)). From \(A\), any number of further a's, then optionally \(B\), which gives any number of b's including none. From the b start, only b's follow. So every string is \(a^{m}b^{n}\) with at least one symbol: \(m \gt 0\) or \(n \gt 0\). The empty string is excluded because \(S\) has no \(\varepsilon\) rule.
The other options get one of these conditions wrong, for example 'm \(\gt\) 0 and n \(\gt\) 0' for \(G_{2}\) would exclude 'a' and 'b', which \(G_{2}\) generates.
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