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.2k views answer comment Share Follow See all 16 Comments See all 16 16 Comments reply Show 13 previous comments 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 gatematesingh commented Nov 10, 2015 reply Follow Share Even c is correct too? 0 votes 0 votes Sachin Mittal 1 commented Dec 21, 2015 reply Follow Share @gatematesingh C is not correct because it does not generate set of all strings that begin and end with the same symbol. aaaaba is not generated by given grammar. 33 votes 33 votes pC commented Jul 20, 2016 i edited by pC Jul 20, 2016 reply Follow Share @sachin_mittal_1 SIR , Questions says that Language generated by above grammar is the set of ____ ( strings that begin and end with the same symbol ) If palindrome means string will begin and end with same symbol . so C is also correct , right ? They didn't asks it in reverse order ie. strings that begin and end with the same symbol is accepted by the grammar . I marked option B because it gives more clarity . I dont feel option C is wrong 2 votes 2 votes Warrior commented May 3, 2017 reply Follow Share Your statement is Wrong bcoz you just consider Palindrome not Odd length Palindromes ,which is given in Option B. We have counter ex for option C,ex- aa, bb . Hence option (B) is the ONLY correct option. 3 votes 3 votes Sahil1994 commented Nov 29, 2017 reply Follow Share @gatematesingh even Epsilon is not generated by this grammar so C is wrong 0 votes 0 votes 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.