The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
+25 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$
asked in Compiler Design by Active (3.7k points)
edited by | 1.9k views

4 Answers

+30 votes
Best answer

option  A 

 C$\Rightarrow$ a 

or, C $\Rightarrow$b 

or, C $\Rightarrow$aCb$\Rightarrow$aaCbb$\Rightarrow$ aaaCbbb .. soon 

at last you have to put either C$\rightarrow$ a or C$\rightarrow$ b 

so production C is used to derive $a^{n+1}b^{n}$ or $a^{n}b^{n+1}$  $n \geq 0$

S$\rightarrow$ AC [Aanbn+1] can make $a^{n+1}b^{n+1}$ as single a can be derived from A [A $\Rightarrow$aA $\Rightarrow$a as A$\rightarrow$ $\epsilon$] , similarly S$\rightarrow$ CB

simple way, ab can be derived from grammar as S$\Rightarrow$ AC $\Rightarrow$aAC $\Rightarrow$aC$\Rightarrow$ ab 

option A is wrong 

option B , language is used to drive $a^{+}b^{*}$ or $a^{*}b^{+}$ , ab will be derived as S$\Rightarrow$aS $\Rightarrow$ab

option B is wrong 

Option C 

C $\Rightarrow$ $\epsilon$

or C $\Rightarrow$ aCb $\Rightarrow$ aaCbb $\Rightarrow$ aaaCbbb  .. soon at last need to put C $\rightarrow$ $\epsilon$

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 for 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$... 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 . 

answered by Veteran (55k points)
edited by
nice explanation  sir ji
Q 84, Option is D !
is ϵ is considered to be part of the language or not?
Why is option b wrong?
@prerna thats generate 'ab' which is not a part of grammer
+9 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.

answered by Active (1.1k points)
can u tell me y (c) cannot b answere
Because c generating epsilon here and which is not acceptable for given language.
+1 vote

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.

answered by Boss (30.7k points)
0 votes
D and B respectively.
answered by Boss (19.7k points)

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

37,939 questions
45,453 answers
48,207 users