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

The Gateway to Computer Science Excellence

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

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

+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.9k
- Engineering Mathematics 7.6k
- Digital Logic 2.9k
- Programming and DS 4.9k
- Algorithms 4.4k
- Theory of Computation 6.2k
- Compiler Design 2.1k
- Databases 4.1k
- CO and Architecture 3.4k
- Computer Networks 4.2k
- Non GATE 1.4k
- Others 1.5k
- Admissions 595
- Exam Queries 573
- Tier 1 Placement Questions 23
- Job Queries 72
- Projects 18

50,833 questions

57,723 answers

199,447 comments

107,825 users