A CFG G is given with the following productions where S is the start symbol, A…
2008
A CFG G is given with the following productions where S is the start symbol, A is a non-terminal and a and b are terminals.
S→aS∣A
A→aAb∣bAa∣ϵ
Which of the following strings is generated by the grammar above?
- A.
aabbaba
- B.
aabaaba
- C.
abababb
- D.
aabbaab
Attempted by 16 students.
Show answer & explanation
Correct answer: D
The grammar has productions S → aS | A and A → aAb | bAa | ε. The non-terminal A generates strings with equal numbers of a's and b's (balanced), while S can generate any number of leading a's before transitioning to A. Therefore, the strings generated by this grammar must have an equal number of a's and b's after any leading a's. The string in option D (aabbaab) has 4 a’s and 3 b’s, which is unbalanced.
S->aS->aaAb->aabAab->aabbAaab->aabbaab.