Discussion
Consider the following context-free grammar \(G\), where \(S\), \(A\), and \(B\) are the variables (non-terminals), \(a\) and \(b\) are the terminal symbols, \(S\) is the start variable, and the rules of \(G\) are described as:
\(S \rightarrow aaB \mid Abb\)
\(A \rightarrow a \mid aA\)
\(B \rightarrow b \mid bB\)
Which ONE of the languages \(L(G)\) is accepted by \(G\)?
Answer: A
The language is \(\{a^{2}b^{n} \mid n \ge 1\} \cup \{a^{n}b^{2} \mid n \ge 1\}\).
B generates \(b^{n}\) for \(n \ge 1\) and A generates \(a^{n}\) for \(n \ge 1\). The first rule \(S \rightarrow aaB\) therefore gives exactly two a's followed by one or more b's, \(a^{2}b^{n}\). The second rule \(S \rightarrow Abb\) gives one or more a's followed by exactly two b's, \(a^{n}b^{2}\). The language is the union of the two.
The other options demand a link between the numbers of a's and b's (such as \(a^{n}b^{n}\) or \(a^{n}b^{2n}\)), but in this grammar the a's and b's are generated by separate rules with nothing tying the counts together. For example aabbb is in L(G) but has unequal counts.
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