Question

Consider the CFG with {S, A, B} as the non-terminal alphabet, {a, b} as the terminal alphabet, S as the start symbol and the following set of production rules

$S\to bA$	$S\to aB$
$A\to a$	$B\to b$
$A\to aS$	$B\to bS$
$A\to bAA$	$B\to aBB$

Which of the following string is generated by the grammar?

• A. aabbab
• B. abbbba
• C. aaaabb
• D. aabbbb

Answer 1

The correct option is A aabbab

$S\Rightarrow aB\Rightarrow aaBB\Rightarrow aabB\Rightarrow aabbS$
$\Rightarrow aabbaB\Rightarrow aabbab.$

So aaabbab is generated by the grammar.