Question

In the context-free grammar below, S is the start symbol, a and b are terminals, and $ϵ$ denotes the empty strings
$S\to$aSAb | $ϵ$
$A\to$ bA | $ϵ$
The grammar generates the language

• A. {$a^m{b}^n|m=n$}
• B. {$a^m{b}^n|m\le n$}
• C. (($a+b{)}^{\ast }b{)}^{\ast }$
• D. $a^{\ast }{b}^{\ast }$

Answer 1

The correct option is B {$a^m{b}^n|m\le n$}

$A\to bA|ϵ$
L(A) = b*
$S\to aSAb|ϵ$
Now, substituting A solution into this gives
$S\to aS{b}^{\ast }b|ϵ$
$S\to aSb|aSbb|aSbbb...|ϵ$
L(S) = {$a^m{b}^n|m\le n$}