Possible Duplicate:
Show that $\{xy \mid |x| = |y|, x\neq y\}$ is context-free
Can anyone prove that the following is a CFL? or not? why?
$$L=\{w=w_1w_2 \mid len(w_1)=len(w_2) \mbox{ and $w_1$ does not equal $w_2$}\}$$
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this communityPossible Duplicate:
Show that $\{xy \mid |x| = |y|, x\neq y\}$ is context-free
Can anyone prove that the following is a CFL? or not? why?
$$L=\{w=w_1w_2 \mid len(w_1)=len(w_2) \mbox{ and $w_1$ does not equal $w_2$}\}$$
This must be a classic in formal language theory. The Pumping Lemma will not help, because, unexpectedly, it is context-free. (I did not see the answer here, but it might be overlooked)
The $w_1$ and $w_2$ parts must have a position where they differ. Unfortunately, we cannot distinguish the middle and the two matching positions at the same time. However, we can find matching positions without knowing the middle.
With some effort you can convince yourself that your language $L$ equals $$\{ x_1 a x_2 b x_3 \mid a,b \in \Sigma, a\neq b, |x_1|+|x_3| = |x_2| \}.$$ Once you have shown that, write a grammar using that formulation.