Part - 2 --> https://gateoverflow.in/79801/gate2006-85

The Gateway to Computer Science Excellence

First time here? Checkout the FAQ!

x

+27 votes

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

- $S\rightarrow AC\mid CB$

$C\rightarrow aCb\mid a\mid b$

$A\rightarrow aA\mid \varepsilon$

$B\rightarrow Bb\mid \varepsilon$

- $S\rightarrow aS\mid Sb \mid a\mid b$

- $S\rightarrow AC\mid CB$

$C\rightarrow aCb\mid \varepsilon$

$A\rightarrow aA\mid \varepsilon$

$B\rightarrow Bb\mid \varepsilon$

- $S\rightarrow AC\mid CB$

$C\rightarrow aCb\mid \varepsilon$

$A\rightarrow aA\mid a$

$B\rightarrow Bb\mid b$

+35 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 [Aa^{n}b^{n+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 .

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

- All categories
- General Aptitude 1.8k
- Engineering Mathematics 7.3k
- Digital Logic 2.9k
- Programming & DS 4.9k
- Algorithms 4.3k
- Theory of Computation 6k
- Compiler Design 2k
- Databases 4.1k
- CO & Architecture 3.4k
- Computer Networks 4.1k
- Non GATE 1.4k
- Others 1.4k
- Admissions 596
- Exam Queries 577
- Tier 1 Placement Questions 23
- Job Queries 72
- Projects 18

49,530 questions

54,139 answers

187,354 comments

71,068 users