The Gateway to Computer Science Excellence
+31 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$
in Compiler Design by Active (3.3k points)
edited by | 3.3k views

in option c we can but A,B,C  equal ε then gammer produce ε but original language do not produce ε 

4 Answers

+41 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 . 

by Veteran (57.1k 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

Answer is D.

Option A is wrong. Here's why:

$S\Rightarrow AC \Rightarrow aA C\Rightarrow aC\Rightarrow ab$

Because it's possible to generate equal a's and b's
+13 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.

by Active (1.2k 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.

by Boss (30.8k points)
0 votes
D and B respectively.
by Boss (19.9k 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
50,833 questions
57,723 answers
107,825 users