GATE Papers >> CSE >> 2019 >> Question No 41

Question No. 41 CSE | GATE 2019

Which one of the following languages over $ \sum\;=\;\{a,\;b\} $ is NOT context-free?

Answer : (C) $ \{wa^nw^Rb^n\vert w\in\{a,\;b\}\ast,\;n\geq0\} $

Solution of Question No 41 of GATE 2019 CSE Paper

Option (C) is not CFL. Since when we insert 'w' in stack and then $ \mathrm a^{\mathrm n}/\mathrm n\geq0 $ then wR come so, now we have to match wR (reverse of w) with 'w' and we have to check whether actually it is reverse of 'w' or not. But in the top of the stack we see only a so, here matching of w and wR is not possible because in between w and wR we get a

ex:  let w = ab, let n = 2 then

wR = ba

So, string = ab aa ba bb

                   w  a2  w  b2

So, for that if we insert w then a2 as show below

New, we have to match wR = ba with 'w' but in the stop of stack we have w so, PDA is not panible for thin language. Hence, it is not regular

But for option (A) we can give PDA because first w come then an come there bn come so, for bn will pop an and then in stack we get w and then wR come so, for that we can do matching so, PDA in possible so, it in CFL

For option (B) we can give NPDA IN option (D) I can be either n, 3n or 5n

$ \mathrm{So},\;\mathrm L=\mathrm a^{\mathrm n}\;\mathrm b^{\mathrm n}\cup\mathrm a^{\mathrm n}\;\mathrm b^{3\mathrm n}\cup\mathrm a^{\mathrm n}\;\mathrm b^{5\mathrm n} $

Since, whenever we can write language in union, we can give NPDA for that language

h84Mvu levitra nizagara

Posted on  18/10/2020 17:43:34  by  dobsonz
rHN1Eq levitra nizagara

Posted on  18/10/2020 18:57:53  by  dobsonz
5YlbOZ viagra cialis buy

Posted on  01/11/2020 19:52:43  by  johnanx
dgpLoV write my essay

Posted on  03/12/2020 23:36:04  by  dobson
gXKcH7 write my essay

Posted on  04/12/2020 02:57:11  by  dobson
lv0y2V xnxx videos

Posted on  13/12/2020 00:03:55  by  johnan
UYqMAD xnxx videos

Posted on  13/12/2020 00:33:11  by  johnan

Posted on  13/12/2020 04:40:23  by  dobson

Posted on  13/12/2020 05:25:29  by  dobson

Posted on  15/12/2020 05:39:42  by  dobson

Posted on  15/12/2020 06:25:36  by  dobson

Posted on  09/01/2021 09:13:43  by  dobson

Posted on  09/01/2021 10:38:07  by  dobson
1utPZW waldorf doll

Posted on  09/01/2021 13:28:00  by  johnanz
9nAiBc waldorf doll

Posted on  09/01/2021 14:55:10  by  johnanz
Leave a comment