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 Show 6 previous comments 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.