34 votes 34 votes $$S \to aSa \mid bSb\mid a\mid b$$ The language generated by the above grammar over the alphabet $\{a,b\}$ is the set of: all palindromes all odd length palindromes strings that begin and end with the same symbol all even length palindromes Theory of Computation gatecse-2009 theory-of-computation grammar easy isro2016 + – Kathleen asked Sep 22, 2014 • retagged Dec 9, 2022 by Lakshman Bhaiya Kathleen 20.4k views answer comment Share Follow See all 16 Comments See all 16 16 Comments reply Shimpy Goyal commented Jun 17, 2015 reply Follow Share y not b & c both or we have to choose very specific???????? 0 votes 0 votes Akash Kanase commented Nov 23, 2015 reply Follow Share There are counter examples for c.So c is not correct. 0 votes 0 votes Mk Utkarsh commented Mar 22, 2018 i edited by Mk Utkarsh Mar 22, 2018 reply Follow Share not able to generate bbab and many other strings. well still this question creates confusion because option c should have been c) all strings that begin and end with the same symbol 0 votes 0 votes abhishekmehta4u commented Mar 22, 2018 reply Follow Share aa is not genrated . In option c 0 votes 0 votes Raj Kumar 7 commented Mar 22, 2018 reply Follow Share In option C, there is not talking about all . All the odd length palindrome have same being and end character. So, i confused. 0 votes 0 votes mesh90 commented Oct 3, 2019 reply Follow Share Because aaba , bbbab, abbbabba these are the string which begin and end with the same symbol but our given grammar unable to generates ..... Hence option C is wrong and Option B is true because of odd length palindrome generates given grammar. 1 votes 1 votes aditya_cracks2021 commented Dec 5, 2020 reply Follow Share because C just says starting and ending with the same symbols, whereas B says odd-length palindromes. All palindromes definitely start and end with the same symbols and as one can easily see it should be of odd length. :) 0 votes 0 votes Abhrajyoti00 commented Oct 18, 2022 reply Follow Share @Arjun Sir, @Sachin Mittal 1 Sir It should have been Multi Select with answers : Both option B and C. As it is a set of all odd length palindromes and also set of strings that begin and end with the same symbol. We can’t disagree that set of all odd length palindromes don’t begin and end with the same symbol. Option B doesn’t say all strings. It says set of strings. 0 votes 0 votes Pranavpurkar commented Oct 26, 2022 reply Follow Share Abhrajyoti00 I think yes ! if it was MSQ then both options B and C must be correct. as in MSQ’s we select all the possible cases. 1 votes 1 votes Abhrajyoti00 commented Oct 26, 2022 reply Follow Share Yes. Infact it must be MSQ. Both are correct. 0 votes 0 votes Pranavpurkar commented Oct 26, 2022 reply Follow Share Abhrajyoti00But , we also cannot deny the fact that all even length palindromes(and many more strings) can also start and end with the same symbol so if this is not an MSQ then option B is the only correct one.because in MCQ we have to select the strongest possible answer .which is option B in this case. 0 votes 0 votes Abhrajyoti00 commented Oct 26, 2022 reply Follow Share But @Pranavpurkar We can’t disagree that set of all odd length palindromes don’t begin and end with the same symbol. Option B doesn’t say all strings. It says set of strings. 0 votes 0 votes Pranavpurkar commented Oct 26, 2022 reply Follow Share Abhrajyoti00 yes you are correct. but if it is an mcq then we can’t select two answer’s right we have to choose the strongest one. in MSQ both will be correct :) 1 votes 1 votes Abhrajyoti00 commented Oct 26, 2022 reply Follow Share @Pranavpurkar Agreed! Bad framing of options 1 votes 1 votes Pranavpurkar commented Oct 26, 2022 reply Follow Share Abhrajyoti00 it all depends on what the question setter wants from us. 1 votes 1 votes tejas96 commented Aug 15, 2023 reply Follow Share @Pranavpurkar no both b and c cant be true, because in option c we can have ‘abaa’ in which first and last symbol is same but it can’t be generated by above grammar 0 votes 0 votes Please log in or register to add a comment.
Best answer 38 votes 38 votes Answer is B. String generated by this language is $a,b,aba,bab,aabaa,\ldots$ All this strings are odd length palindromes. neha pawar answered Oct 15, 2014 • edited Jun 21, 2021 by Lakshman Bhaiya neha pawar comment Share Follow See all 8 Comments See all 8 8 Comments reply Show 5 previous comments Niraj Singh 2 commented Dec 5, 2017 reply Follow Share but it is not written that grammar should generate all strings that begin and end with same symbol option C should be " all strings that begin and end with same symbol" then it is correct to remove option c is it not? 1 votes 1 votes suryaprakash commented Feb 8, 2018 reply Follow Share even ur answer contains flaw the language u given covers BOTH B and C. 0 votes 0 votes talha hashim commented Jan 24, 2019 reply Follow Share aa is starting and ending with same symbal but not cover by above grammar.so option C) is wrong.only option B) is correct 2 votes 2 votes Please log in or register to add a comment.
17 votes 17 votes (A) Counter Example :- aa or bb not generated by above Grammar. (C) Counter example :- aa not genetrated by above Grammer. (D) Counter Example :- aa not generated, but a generated. (B) Correct. Odd length palindromes are generated by this grammar. Akash Kanase answered Nov 14, 2015 Akash Kanase comment Share Follow See all 0 reply Please log in or register to add a comment.
14 votes 14 votes option b abhishekmehta4u answered Mar 22, 2018 abhishekmehta4u comment Share Follow See all 4 Comments See all 4 4 Comments reply Raj Kumar 7 commented Mar 22, 2018 reply Follow Share I agree with you but I am asking about if all do not mention we assume that it talking about all. As in option C. 0 votes 0 votes abhishekmehta4u commented Mar 22, 2018 reply Follow Share In option c it is saying it genrate starting and ending with same symble. But it can't genrate all string like string aa. So it is wrong. 0 votes 0 votes abhishekmehta4u commented Mar 22, 2018 reply Follow Share Yes it genrate all string . Not subset of string 0 votes 0 votes Raj Kumar 7 commented Mar 22, 2018 reply Follow Share Thanks Bro!! 0 votes 0 votes Please log in or register to add a comment.
8 votes 8 votes (B) all odd length palindromes Arjun answered Oct 15, 2014 Arjun comment Share Follow See all 0 reply Please log in or register to add a comment.