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

Question

Consider the grammar given below:

$S \rightarrow x \ T \mid  y \ Z$

$Z \rightarrow x \mid  x \ S \mid y \ Z \ Z$

$T \rightarrow y \mid y \ S \mid y \ T \ T$

Consider the following strings:

1. $xxyyx$
2. $xxyyxy$
3. $xyxy$
4. $yxxy$
5. $yyxxyx$
6. $xyx$

Which of the above strings are generated by the given grammar?

• A. i, iv and iii
• B. ii, iii and iv
• C. ii, v and iv
• D. iii, iv and v

Comments

S

/\

y Z

   /\\

 y Z Z

    |   |

    S   x

    /\

   x T

     |

     y

yyxxyx is generated..

like that (iii) and (iv) also generated.

Answer 1

Option D , iii, iv and v is possible grammars.

 

Answer 2

Extremely fast method if you read options before solving:

 

1. Strings i and ii have ‘xx‘ at the start. Looking at the grammar, it expands to the right, so we have to produce xx from the starting terminal.
2. S → xT →xy | xyS | xyTT .  So xx is not possible, Therefore both i and ii are not possible. 
3. In options, only option D has no i and ii.

Therefore option D is answer.