Pumping Lemma

Question

If L = { x == y | where x and y are equal binary numbers} and Σ = {0, 1, =}

How can I prove that L is not a regular language using pumping lemma and contradiction?

Answer 1

Take a string $w$ which belongs to that language $L$.

Let, $w$ be $01^k==01^k$.

Dividing $w$ into $xyz$ where $|xy|$ is our pumping length and $|y|>=1.$

Let, $x=0, y=1^i, z=(1^{k-1}==1^k0)$,

Then, $w=(x.y.z)=(0.1.1^{k-1}==1^k0)$

According to the pumping lemma if $y$ is pumped $i$ times, then for all $i$ it must also belong to $L$.

So, $xy^iz=(0.(1)^i.(1)^{k-1}==1^k0)$.

You can see for except for $i=1$, $xy^iz$ will not belong to $L$. So, $L$ must not be Regular.