12 votes 12 votes Design a context free grammar for the language consisting of all strings over $\mathbf{\{a,b\}}$ that are not the form $\mathbf{ww}$ for any string $\mathbf{w}$ Theory of Computation pushdown-automata theory-of-computation isi2015 + – Devasish Ghosh asked Mar 9, 2017 • edited Feb 27, 2018 by kenzou Devasish Ghosh 1.4k views answer comment Share Follow See all 0 reply Please log in or register to add a comment.
Best answer 20 votes 20 votes Now, this is what we called a problem. Here is the grammar, $ S \to E \mid U \mid \epsilon $ $ E \to AB \mid BA $ $ A \to ZAZ \mid a $ $ B \to ZBZ \mid b $ $ U \to ZUZ \mid Z $ $ Z \to a \mid b $ For more Explore this. rude answered Mar 9, 2017 • edited Feb 27, 2018 by kenzou rude comment Share Follow See all 9 Comments See all 9 9 Comments reply ana commented Aug 12, 2017 reply Follow Share how can we generate 'abba' with this grammar? 0 votes 0 votes Gate Ranker18 commented Sep 2, 2017 reply Follow Share ana S->E->BA->ZBZA->aBZA->abZA->abbA->abba 1 votes 1 votes set2018 commented Nov 1, 2017 reply Follow Share what are the basic steps for generate grammar ? 0 votes 0 votes Puja Mishra commented Jan 15, 2018 reply Follow Share #rude .... can u tell me how did u approach that problem ?? 0 votes 0 votes HeadShot commented Sep 10, 2018 reply Follow Share @Puja Mishra Go through that pdf. Nicely explained. It is hard to generate if we never encountered it before. 0 votes 0 votes AIR_1 commented Sep 17, 2018 i reshown by AIR_1 Sep 18, 2018 reply Follow Share How to generate "abbbabba'' ? I'm not able to generate it. 1 votes 1 votes MiNiPanda commented Sep 18, 2018 reply Follow Share S-> E-> BA -> ZBZA -> ZZBZZA -> ZZZBZZZA-> abbbabba 2 votes 2 votes AIR_1 commented Sep 18, 2018 reply Follow Share Got it. Thank you!! 0 votes 0 votes indranil21 commented Sep 3, 2020 reply Follow Share ϵ should not be derived. AND ‘’aaba” can not be generated using this grammar though it is in the language. 0 votes 0 votes Please log in or register to add a comment.