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?
Answer: D. aabbaab — 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…
- A.
aabbaba
- B.
aabaaba
- C.
abababb
- D.
aabbaab
Attempted by 30 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.
Explore the full course: Iocl Engineers Officers Grade A Paper 2