edited by
7,426 views
27 votes
27 votes

Consider the grammar given below:

$S      \rightarrow      x \ B \mid y \ A$
$A      \rightarrow      x \mid x \ S \mid y \ A \ A$
$B      \rightarrow      y \mid y \ S \mid x \ B \ B$

Consider the following strings.

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

Which of the above strings are generated by the grammar ?

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

2 Answers

Best answer
37 votes
37 votes

ii, iii and iv.

So, option is correct.

Above grammar is for equal no of x and y 

from Non-terminal $S \rightarrow xB$                            

                                   $\Rightarrow xy$    [as $B \rightarrow y$ one $y$ for one $x$]                               

$S \rightarrow xB$

$\Rightarrow xxBB$   [as $B \rightarrow yBB$   one $B$ result in one $y$ for one $x$ ]

$S \rightarrow xB$

$\Rightarrow xyS$ [as $B \rightarrow yS$  one $y$ for one $x$ and start again]

Note: Same applies for string start with $y$ i.e .  $S \rightarrow yA$.

edited by
4 votes
4 votes

ii) xxyyxy
S → xB
S → xxBB
S → xxyB
S → xxyyS
S → xxyyxB
S → xxyyxy

 

(iii) xyxy
S → xB
S → xyS
S → xyxB
S → xyxy

 

(iv) yxxy
S → yA
S → yxS
S → yxxB
S → yxxy

Answer:

Related questions

67 votes
67 votes
3 answers
1
Ishrat Jahan asked Oct 30, 2014
12,632 views
Consider the following grammars. Names representing terminals have been specified in capital letters.$$\begin{array}{llll}\hline \text{$G1$ :} & \text{stmnt} & \text{$\...
42 votes
42 votes
7 answers
4
Ishrat Jahan asked Oct 30, 2014
7,776 views
Consider the regular expression $R = (a + b)^* (aa + bb) (a + b)^*$Which deterministic finite automaton accepts the language represented by the regular expression $R$?