3.3k views

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 | 3.3k views
+1
0

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

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
0
nice explanation  sir ji
+1
Q 84, Option is D !
+1
yes
0
is ϵ is considered to be part of the language or not?
–1
Why is option b wrong?
0
@prerna thats generate 'ab' which is not a part of grammer
+1

0
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
0
Right!

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.

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

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)
D and B respectively.
by Boss (19.9k points)