Topic: Theory of Computation
Which of the following strings will correctly match the Grammar G represented by production rules given?
$S\rightarrow A|B$
$A\rightarrow aAb | c$
$B\rightarrow bBd | e$
- A. accbb
- B. aacbb
- C. abaed
- D. aaebb
Answer: B. aacbb
Explanation: From the production rules:
$A \rightarrow aAb | c$ generates strings of the form $a^n c b^n$ where $n \ge 0$.
$B \rightarrow bBd | e$ generates strings of the form $b^m e d^m$ where $m \ge 0$.
The language generated by S is the union of these two sets: $\\{a^n c b^n\\} \cup \\{b^m e d^m\\}$.
Checking the options, 'aacbb' matches the pattern $a^n c b^n$ with $n=2$ ($a^2 c b^2$). The other options do not match either pattern.