Test by Bikram | Theory of Computation | Test 2 | Question: 30

Question

The language generated by the following grammar is:

• $S \rightarrow  aAb$
• $A \rightarrow aAb / B$
• $B \rightarrow  CC$
• $C \rightarrow  bDa$
• $D \rightarrow  bDa / \epsilon$

• A. $\{ {a^m \;b^n \;a^n\; b^p \;a^p\; b^m } \mid m,n,p > 0\;\}$
• B. $\{ {a^m \;b^n\; a^m\; b^n\; a^m\; b^n } \mid  m,n,p >0\; \}$
• C. $\{ { a^m\; b^n\; a^p\; b^p \;a^n\; b^m } \mid  m,n,p > 0 \;\}$
• D. $\{ { a^m\; b^m \;a^n\; b^n \;a^p\; b^p } \mid m,n,p > 0\; \}$

Comments

@Bikram sir,

this string is satisfied by option 'A'   but not by option 'C'...

therefore option A should be correct.  

---

yes @joshi should be option A

Answer 1

Let's take some string:

$S\rightarrow aAb\rightarrow aaAbb\rightarrow aaBbb\rightarrow aaCCbb\rightarrow aabDaCbb\rightarrow aabDabDabb\rightarrow aabababb\rightarrow a^2b^1a^1b^1a^1b^2$

 

Option B and D eliminated.

 

$S\rightarrow aAb\rightarrow aBb\rightarrow aCCb\rightarrow abDaCb\rightarrow abDabDab\rightarrow abbDaabDab\rightarrow abbaabDab\rightarrow abbaabab\rightarrow a^1b^2a^2b^1a^1b^1$

 

Option C eliminated.

---

$Ans:A$