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 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.