Identify the language generated by the following grammar, where S is the start variable.

S - XY
X - aX | a
Y - aYb |...

Question

Identify the language generated by the following grammar, where S is the start variable.

S -> XY
X -> aX | a
Y -> aYb | epsilon

A. {a^m b^n | m >= n, n >= 0}
B. {a^m b^n | m > n, n >= 0}
C. {a^m b^n | m >= n, n >= 0}
D. {a^m b^n | m > n, n >= 0}

Accepted Answer

The language is {a^m b^n | m > n, n >= 0}. Answer: B. We have a grammar with three productions. S generates X followed by Y. X generates one or more a's (at least one a). Y generates equal numbers of a's and b's (i.e., a^k b^k for k >= 0, because Y -> aYb | epsilon). So S generates a string of a's (from X, at least 1) concatenated with a^k b^k (from Y, k >= 0). The total number of a's is at least 1 + k and number of b's is exactly k, so m >= n with n >= 0.

Identify the language generated by the following grammar, where S is the start variable. S -> XY X -> aX | a Y -> aYb | epsilon A. {a^m b^n | m >= n, n >= 0} B. {a^m b^n | m > n, n >= 0} C. {a^m b^n | m >= n, n >= 0} D. {a^m b^n | m > n, n >= 0}