in Theory of Computation edited by
1,078 views
11 votes
11 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}$
in Theory of Computation edited by
1.1k views

1 Answer

19 votes
19 votes
Best answer

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.

edited by
by

4 Comments

S-> E-> BA -> ZBZA -> ZZBZZA -> ZZZBZZZA-> abbbabba
2
2
Got it. Thank you!!
0
0

 

ϵ should not be derived.

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

 

 

 

0
0

Related questions