ISI 2015 PCB C4 A

Question

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}$

Answer 1

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.

Comments

S-> E-> BA -> ZBZA -> ZZBZZA -> ZZZBZZZA-> abbbabba

---

Got it. Thank you!!

---

 

ϵ should not be derived.

AND ‘’aaba” can not be generated using this grammar though it is in the language.