edited by
876 views
2 votes
2 votes
$ L= \{ w1 w2 |  w1,w2 ∈Σ^{+} ,w1!=w2 \} $

How can i prove that it is CFL?
edited by

1 Answer

1 votes
1 votes

$L$  =  $\left \{ W_1W_2 \, \, \mid \, \, W_1,W_2 \in \Sigma^* \, \, and \, \, W_1 \, \neq \, W_2\right \}$

It is a Regular language and thus CFL. Every String, except $ \epsilon $ , can be written in this form. i.e. Every String (Except Null String) can be split in Two parts which are not equal.

Say, $w = a$ is the String. So, we can split it in two such parts which are not equal like this :  $\epsilon.a$ where $W_1 \, is\, \epsilon$  and $W_2 \, is\, a $

Thus, the language is $\Sigma^*  -\, \left \{ \epsilon\right \}$


If  $L$  =  $\left \{ W_1W_2 \, \, \mid \, \, W_1,W_2 \in \Sigma^+ \, \, and \, \, W_1 \, \neq \, W_2\right \}$

then the language will contain all Strings except $\epsilon,a,b,aa,bb$  because for any other string (Except $\epsilon,a,b,aa,bb$ ), we can split the string in such two parts which are not equal. For instance, let $w = aaaa$  then We can split it like this where  $W_1 \, is\, a$  and $W_2 \, is\, aaa$ , Thus $W_1 \neq W_2$ And so this String will belong to the language. 


From the Comments, 

This language (Language in the question, Which has been changed once, If you don't change it again) in the question is indeed Regular But You are confusing it with "Complement of $WW$". 

The Complement of $WW$ is as follows :

$L^c = \left \{ Set \, of\, All\, \, Odd\, \, length \, \, Strings\, \right \} \bigcup \left \{ W_1W_2\, \, \mid \, \, W_1,W_2 \in \Sigma^* \, \, and \, \, \, W_1 \neq W_2 \, \, \, and \, \, \left | W_1 \right | = \left | W_2 \right | \, \, \right \}$ 

NOTE that $\left | W_1 \right | = \left | W_2 \right |$ is an Important condition here Which makes it Non-Regular and Complement of $WW$


To See Why Complement of $WW$ is CFL, Use the CFG method. If One can give CFG for it then that's enough to declare it CFL. PDA construction is not easily understandable for it and requires more intuition. You can check the CFG for it in the link provided in the comments. 

edited by

Related questions

1 votes
1 votes
1 answer
4