45 votes 45 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$ Compiler Design gatecse-2006 compiler-design grammar normal theory-of-computation + – Rucha Shelke asked Sep 26, 2014 edited Nov 29, 2017 by kenzou Rucha Shelke 12.0k views answer comment Share Follow See all 3 Comments See all 3 3 Comments reply Chhotu commented Jan 1, 2018 reply Follow Share Part - 2 --> https://gateoverflow.in/79801/gate2006-85 2 votes 2 votes mohan123 commented Sep 23, 2019 reply Follow Share in option c we can but A,B,C equal ε then gammer produce ε but original language do not produce ε 1 votes 1 votes svas7246 commented Nov 16, 2021 reply Follow Share Basically before going to solution this question is about whether we can generate strings like ab,aabb,aaabbb Given these grammars if they are able to produce string like above then they are wrong Point to consider those grammars which produce strings containing equal number of a’s and b’s can even produce strings of unequal a’s and b’s but if a grammar is able to produce equal number of a’s and b’s along with unequal a’s and b’s it should not be considered That one Grammar which only produces unequal a’s and b’s is the answer we need to find it 0 votes 0 votes Please log in or register to add a comment.
Best answer 57 votes 57 votes Lets consider options one by one. Option A $C\Rightarrow a$ or, $C \Rightarrow b $ or, $C \Rightarrow aCb \Rightarrow aaCbb \Rightarrow aaaCbbb \ldots $ so on and at last we have to put either $C\rightarrow a$ or $C\rightarrow b$ So production starting with $C$ is used to derive $a^{n+1}b^{n}$ or $a^{n}b^{n+1} ; n \geq 0$ $S\rightarrow AC [Aa^nb^{n+1}]$ can make $a^{n+1}b^{n+1}$ as a single $a$ can be derived from $A [A \Rightarrow aA \Rightarrow a$ as $A\rightarrow \varepsilon$], similarly $S\rightarrow CB$ In a simple way, $ab$ can be derived from grammar as $S\Rightarrow AC \Rightarrow aAC \Rightarrow aC\Rightarrow ab$ option A is wrong Option B Corresponding language is $a^{+}b^{\ast}$ or $a^{\ast}b^{+},$ and $ab$ can be derived as $S\Rightarrow aS \Rightarrow ab$ option B is wrong Option C $C \Rightarrow \varepsilon$ or $C \Rightarrow aCb \Rightarrow aaCbb \Rightarrow aaaCbbb \ldots$ so on and at last need to put $C \rightarrow \varepsilon$ 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 to 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 \ldots 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 . Praveen Saini answered May 19, 2015 edited Jun 4, 2021 by Arjun Praveen Saini comment Share Follow See all 10 Comments See all 10 10 Comments reply Show 7 previous comments d3ba commented Nov 23, 2019 reply Follow Share 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 2 votes 2 votes `JEET commented Nov 23, 2019 reply Follow Share Right! 0 votes 0 votes RRajeev commented Jan 8, 2021 reply Follow Share for Option ‘A’ can easily generate strings with equal no of a`s and b`s, S→ CB → aB → aBb → ab 0 votes 0 votes Please log in or register to add a comment.
15 votes 15 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. Dhananjay answered Jan 7, 2015 Dhananjay comment Share Follow See all 2 Comments See all 2 2 Comments reply Nisha kumari commented Feb 4, 2015 reply Follow Share can u tell me y (c) cannot b answere 0 votes 0 votes LeenSharma commented May 18, 2015 reply Follow Share Because c generating epsilon here and which is not acceptable for given language. 1 votes 1 votes Please log in or register to add a comment.
1 votes 1 votes Q.84 answer = Option DQ.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. amarVashishth answered Nov 16, 2015 amarVashishth comment Share Follow See all 0 reply Please log in or register to add a comment.
0 votes 0 votes D and B respectively. Gate Keeda answered Oct 28, 2014 Gate Keeda comment Share Follow See all 0 reply Please log in or register to add a comment.