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

Question

Match the following lists.

The conditions on the language description $L = \{a^i \ b^j \ c^k\}$ are given in List I and respective grammars are given in List II.

$\begin{array}{|c|c|c|c|} \hline {} & \text{List I} & {} & \text{List II} \\ \hline A. & k=i+j & G_1: & S \rightarrow aSc\mid B;  B \rightarrow aBb\mid \epsilon  \\ \hline B. & k=i+2j & G_2: & S \rightarrow aSc\mid B; B \rightarrow bBcc\mid \epsilon \\ \hline C. & i=j+k & G_3: & S \rightarrow aSc\mid B; B \rightarrow bBc \mid \epsilon \\ \hline \end{array}$

• A. $A:G_1, B:G_2, C:G_3$
• B. $A:G_3, B:G_2, C:G_1$
• C. $A:G_1, B:G_3, C:G_2$
• D. $A:G_3, B:G_1, C:G_2$

Answer 1

$G3:$ Take some string:

$S\rightarrow aSc\rightarrow aaScc\rightarrow aaBcc\rightarrow aabBccc\rightarrow aabccc: a^2b^1c^3(a^ib^jc^k):k=i+j:A$

Option A and C eliminated

 

$G1:$ Take some string:

$S\rightarrow aSc\rightarrow aaScc\rightarrow aaBcc\rightarrow aaaBbcc\rightarrow aaabcc: a^3b^1c^2(a^ib^jc^k):i=j+k:C$

Option D eliminated

---

$Ans: B$