edited by
11,996 views
45 votes
45 votes

Which one of the following grammars generates the language $ L=\left \{ a^{i}b^{j}\mid i\neq j \right \}$?

  1. $S\rightarrow AC\mid CB$
    $C\rightarrow aCb\mid a\mid b$
    $A\rightarrow aA\mid \varepsilon$
    $B\rightarrow Bb\mid \varepsilon$
     
  2. $S\rightarrow aS\mid Sb \mid a\mid b$
     
  3. $S\rightarrow AC\mid CB$
    $C\rightarrow aCb\mid \varepsilon$
    $A\rightarrow aA\mid \varepsilon$
    $B\rightarrow Bb\mid \varepsilon$
     
  4. $S\rightarrow AC\mid CB$
    $C\rightarrow aCb\mid \varepsilon$
    $A\rightarrow aA\mid a$
    $B\rightarrow Bb\mid b$
edited by

4 Answers

Best answer
57 votes
57 votes

Lets consider options one by one.

Option  A 

  • $C\Rightarrow a$ 
  • or, $C \Rightarrow b $
  • or, $C \Rightarrow aCb \Rightarrow aaCbb \Rightarrow  aaaCbbb \ldots $ so on and at last we have to put either $C\rightarrow a$ or $C\rightarrow b$ 
  • So production starting with $C$ is used to derive $a^{n+1}b^{n}$ or $a^{n}b^{n+1} ; n \geq 0$
  • $S\rightarrow AC [Aa^nb^{n+1}]$ can make $a^{n+1}b^{n+1}$ as a single $a$ can be derived from $A [A \Rightarrow aA \Rightarrow a$ as $A\rightarrow \varepsilon$], similarly $S\rightarrow CB$
  • In a simple way, $ab$ can be derived from grammar as $S\Rightarrow AC \Rightarrow aAC \Rightarrow aC\Rightarrow ab$ 
  • option A is wrong 

Option B 

  • Corresponding language is $a^{+}b^{\ast}$ or $a^{\ast}b^{+},$ and $ab$ can be derived as $S\Rightarrow aS \Rightarrow ab$
  • option B is wrong 

Option C 

  • $C \Rightarrow \varepsilon$
  • or $C \Rightarrow  aCb \Rightarrow aaCbb \Rightarrow aaaCbbb \ldots$ so on and at last need to put $C \rightarrow \varepsilon$
  • Production $C$ will generate $a^{n}b^{n} ; n \geq 0$ 
  • $S\rightarrow AC$  can generate $a^{n}b^{n}$ as $A$ can be $\epsilon,$ similarly $S \rightarrow CB$
  • option C is wrong 

Option D .

  • Production $C$ is used to generate $a^{n}b^{n}$ as in option $C$
  • $S\rightarrow AC$ will increase no of $a$'s before $a^{n}b^{n}$ as $A$ will generate $a$ or $aa$ or $aaa \ldots i,e., a^+,$ so $S\rightarrow AC$ will generate $a^{+}a^{n}b^{n} , i.e., a^{i}b^{j} ; i>j$ 
  • $S \rightarrow CB$ will generate $a^{n}b^{n}b^{+}\;  i.e.,  a^{i}b^{j} ; i<j$ 
  • option D is right . 
edited by
15 votes
15 votes

Q. 84

By seeing the question, we know the strings of form ab, aabb, aaabbb...... are not possible.  Epsilon is also not possible.

Now, just check the options with the string ab.

Option A, B, C are generating ab.

So, correct answer is D.

1 votes
1 votes

Q.84 answer = Option D
Q.85 answer = Option A

try generating random strings from the given grammars in the options that provide may a counter to the given Language.
Once done with that values of $l$ and $m$ will clear out, try value putting with an adequate big string in length to check which option is correct.

Answer:

Related questions

33 votes
33 votes
4 answers
2