# Could anyone prove that this is a context free language or not? [duplicate]

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

-

## migrated from cstheory.stackexchange.comJan 27 '13 at 12:46

This question came from our site for theoretical computer scientists and researchers in related fields.

## marked as duplicate by A.Schulz, Pål GD, Merbs, Raphael♦Jan 28 '13 at 10:07

What have you tried? Have you tried making a PDA? Do you know the pumping lemma for CFLs? – Pål GD Jan 27 '13 at 13:43

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.