edited by
26,530 views
59 votes
59 votes

Consider the following context-free grammars;

$G_1 : S \to aS \mid B, B \to b \mid bB$

$G_2 : S \to aA \mid bB, A \to aA \mid B \mid \varepsilon,B \to bB \mid \varepsilon$

Which one of the following pairs of languages is generated by $G_1$ and $G_2$ ,respectively?

  1.  $\{ a^mb^n \mid m > 0 \text{ or } n >0\}$ and $\{ a^mb^n \mid m > 0 \text{ and } n >0\}$ 
  2.  $\{ a^mb^n \mid m > 0 \text{ and } n >0\}$ and $\{ a^mb^n \mid m > 0 \text{ or } n\geq0\}$
  3.  $\{ a^mb^n \mid m \geq 0 \text{ or } n >0\}$ and $\{ a^mb^n \mid m > 0\text{ and } n>0\}$
  4.  $\{ a^mb^n \mid m \geq 0 \text{ and } n >0\}$ and $\{ a^mb^n \mid m > 0 \text{ or } n>0\}$
edited by

8 Answers

Best answer
85 votes
85 votes

Answer is (D).

$G_1$ results in strings $b, ab, bb, aab, abb, bbb,$ ... i.e $a^mb^n$, $m\geq 0$ and $n > 0$ (and because only $a$'s are not possible but only $b$'s are)

$G_2$ result in strings $a, b, aa, ab, bb, aaa, aab, abb, bbb$   ... i.e $a^mb^n$, $m > 0$ or $n > 0$ (or because only $b$'s is possible $b,bb,bbb,$ , only $a$'s are possible)

selected by
41 votes
41 votes

if we have given  right linear grammar,,,then it  is better to draw FA and then analyze the language

and we know null production corrresponds to final state and unit production corresponds to null moves  

now it is clear that

L1 = a* b*b = a*b+    {ambn , m>=0 and  n>0}

and 

L2 = aa* + bb* +  ab+ = a+ + b+  ab+     =  {ambn , m>0 or  n>0}

9 votes
9 votes
my ans is D.

beacuse in G1, a may be 0 or more... but we have to generate b.. "and" will be used in side g1.. not "or"

only option D consist it..no need to check G2 then.

plz correct me if wrong
1 votes
1 votes

(D) is correct..No need to check for G2, bcoz clarfying G1 there is no matching in 1st phase in any other option.

Answer:

Related questions