# Proof that language is not regular. $L=\{w\bar{w}|w\in \{0,1\}^* and\ \bar{w}\ is\ one's\ complement\ of\ w\}$

I'm trying to proof that the following language is not regular using pumping lemma. $$L=\{w\bar{w}|w\in \{0,1\}^* and\ \bar{w}\ is\ one's\ complement\ of\ w\}$$

I started by stating that:

$$|w\bar{w}| = 2p = |xyz|$$

Because of Pumping Lemma the following has to be true:

$$1 \leq |y| \leq |xy| \leq p$$

Because $$|xy| \leq p$$ and $$|w|=|\bar{w}|$$ have to be true, $$\bar{w}$$ has to be completly in $$z$$. I now tried somehow to manipulate the first half, so that it always evaluates to a contradiction, but I am stuck.

• You need to add “for all” or “exists” here and there, or you can’t get anywhere. Feb 3, 2020 at 21:00

Just show that after processing $$0^n$$ and $$0^{n’}$$ with n != n’ you must have reached two different states. (Which is easy: In one state, processing $$1^n$$ leads to an accepting state, in the other state it doesn’t). Therefore there is no finite set of states.
Or you just take the pumping lemma, p arbitrary large, and w = $$0^p 1^p$$. Which makes y = $$0^k$$ for some k >= 1.