GATE CSE 2015 Set 2 | Question: 35

Question

Consider the alphabet $\Sigma = \{0, 1\}$, the null/empty string $\lambda$ and the set of strings $X_0, X_1, \text{ and } X_2$ generated by the corresponding non-terminals of a regular grammar. $X_0, X_1, \text{ and } X_2$ are related as follows.

• $X_0 = 1 X_1$
• $X_1 = 0 X_1 + 1 X_2$
• $X_2 = 0 X_1 + \{ \lambda \}$

Which one of the following choices precisely represents the strings in $X_0$?

• A. $10(0^*+(10)^*)1$
• B. $10(0^*+(10)^*)^*1$
• C. $1(0+10)^*1$
• D. $10(0+10)^*1 +110(0+10)^*1$

Comments

the smallest string accepted by the grammar is 11. A,B,D do not accept 11, therefore can’t be answers

---

In this type of question first check the base case first word that cen be generated by the grammar which is 11 and only option three can generate 11 therefore answer is 3.

---

verify by taking the smallest string generated by the given grammar which is “11”.

option c only accepts.

Answer 1

X0-->1X1

     -->11X2

     -->11^

So smallest possible string is 11.

Only possible option is C which generates this string. Also, option C generates all the possible strings of the language.

So C is the answer.

Answer 2

Simple Normal method

Just expand the equations given,

$X_{0} \rightarrow 1X_{1} \\ \rightarrow 1(0X_{1} + 1X_{2}) \\ \rightarrow 10X_{1} + 11X_{2} \\ \rightarrow 10X_{1} + 11(0X_{1} + \lambda) \\\displaystyle \displaystyle \rightarrow 10X_{1} + 110X_{1} + 11$

 

Now, just observe. 11 should be present in the Regular Expression. Only Option C contains 11.

So answer is Option C.

Answer 3

A Small string 11 will do the work, check with the options only Option C will satisfy it.

One can only watch the relations given in the form of equations, take the smallest string accepted by the grammar and match with the options.

 

Answer 4

By substituting X2 in X1. Then multiplying X1 with 1  to get X0. The expression becomes-

X0 = 10 X1 + 110 X2 + 11

on observing, none of option can derieve string 11 except option C. Hence option C is the answer