Consider the following context-free grammars: \(G_1 : S \to aS \mid B, B \to b…
2016
Consider the following context-free grammars:
\(G_1 : S \to aS \mid B, B \to b \mid bB\)
\(G_2 : S \to aA \mid bB, A \to aA \mid B \mid \varepsilon,B \to bB \mid \varepsilon\)
Which one of the following pairs of languages is generated by \(G_1\) and \(G_2\), respectively?
- A.
\(\{ a^mb^n \mid m > 0 \text{ or } n >0\}\)and\(\{ a^mb^n \mid m > 0 \text{ and } n >0\}\) - B.
\(\{ a^mb^n \mid m > 0 \text{ and } n >0\}\)and\(\{ a^mb^n \mid m > 0 \text{ or } n\geq0\}\) - C.
\(\{ a^mb^n \mid m \geq 0 \text{ or } n >0\}\)and\(\{ a^mb^n \mid m > 0\text{ and } n>0\}\) - D.
\(\{ a^mb^n \mid m \geq 0 \text{ and } n >0\}\)and\(\{ a^mb^n \mid m > 0 \text{ or } n>0\}\)
Attempted by 72 students.
Show answer & explanation
Correct answer: D
Answer: { a^m b^n | m ≥ 0 and n > 0 } and { a^m b^n | m > 0 or n > 0 }
G1: S → aS | B, B → b | bB. B produces b^n with n ≥ 1, and S can prepend any number of a's (including zero), so L(G1) = { a^m b^n | m ≥ 0, n > 0 }.
G2: S → aA | bB. From S → aA we get at least one a and then A can produce more a's or switch to B or ε, giving a^m b^n with m ≥ 1, n ≥ 0. From S → bB we get b^n with n ≥ 1. The union is { a^m b^n | m > 0 or n > 0 } (all non-empty strings of a^*b^*).
A video solution is available for this question — log in and enroll to watch it.