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

Comments
h84Mvu http://pills2sale.com/ levitra nizagara

Posted on  18/10/2020 17:43:34  by  dobsonz
rHN1Eq http://pills2sale.com/ levitra nizagara

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

Posted on  01/11/2020 19:52:43  by  johnanx
dgpLoV https://www.quora.com/What-the-top-SEO-keywords-for-essay-you-know/answer/Alan-Smith-1772 write my essay

Posted on  03/12/2020 23:36:04  by  dobson
gXKcH7 https://www.quora.com/What-the-top-SEO-keywords-for-essay-you-know/answer/Alan-Smith-1772 write my essay

Posted on  04/12/2020 02:57:11  by  dobson
lv0y2V http://xnxx.in.net/ xnxx videos

Posted on  13/12/2020 00:03:55  by  johnan
UYqMAD http://xnxx.in.net/ xnxx videos

Posted on  13/12/2020 00:33:11  by  johnan
dH2R6R https://writemyessayforme.web.fc2.com/

Posted on  13/12/2020 04:40:23  by  dobson
hdR0er https://writemyessayforme.web.fc2.com/

Posted on  13/12/2020 05:25:29  by  dobson
ZKd6Hr https://writemyessayforme.web.fc2.com/#writemyessay

Posted on  15/12/2020 05:39:42  by  dobson
vNFbbm https://writemyessayforme.web.fc2.com/#writemyessay

Posted on  15/12/2020 06:25:36  by  dobson
vVJU1u https://writemyessayforme.web.fc2.com/octavio-paz-essay-day-of-the-dead.html

Posted on  09/01/2021 09:13:43  by  dobson
tl8XVu https://writemyessayforme.web.fc2.com/octavio-paz-essay-day-of-the-dead.html

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

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

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