retagged by
333 views
0 votes
0 votes

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?

  1. i, iv and iii
  2. ii, iii and iv
  3. ii, v and iv
  4. iii, iv and v
retagged by

2 Answers

Best answer
1 votes
1 votes
Option D , iii, iv and v is possible grammars.

 

selected by
0 votes
0 votes

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.

Answer:

Related questions

4 votes
4 votes
0 answers
2
Bikram asked Aug 12, 2017
607 views
The number of possible finite automata with two states $a0$ and $a1$ (where $a0$ is always the initial state over the alphabet $\{p, q\}$) which accepts empty language is...
0 votes
0 votes
1 answer
3
Bikram asked Aug 12, 2017
260 views
What is the regular expression corresponding to the above DFA?$(01 + (00)^*1)^*$$0^*10^*$$(10 + 0(00)^* (1 + 01) )^*$$0(00)^*10^*$