Identify the language generated by the following grammar, where \(S\) is the…
2017
Identify the language generated by the following grammar, where \(S\) is the start variable.
\(S \rightarrow XY\)
\(X \rightarrow aX \mid a\)
\(Y \rightarrow aYb \mid \epsilon\)
- A.
\(\{a^mb^n \mid m \geq n, n > 0 \}\) - B.
\(\{ a^mb^n \mid m \geq n, n \geq 0 \}\) - C.
\(\{a^mb^n \mid m > n, n \geq 0 \}\) - D.
\(\{a^mb^n \mid m > n, n > 0 \}\)
Attempted by 88 students.
Show answer & explanation
Correct answer: C
Key idea: split the grammar into what X and Y generate and then concatenate.
X -> aX | a produces one or more a's, i.e. strings a^m0 with m0 >= 1.
Y -> aYb | ε produces strings of the form a^n b^n with n >= 0 (including the empty string when n = 0).
Concatenating X and Y gives a^(m0+n) b^n, where m0 >= 1 and n >= 0. Let p = m0 + n, then p > n and n >= 0.
Therefore the language is { a^p b^n | p > n, n >= 0 }. Examples include a, aa, aab, aaab, aabb, etc., but strings with equal numbers of a's and b's (like a b) are not generated.
A video solution is available for this question — log in and enroll to watch it.