# Proofs using the regular pumping lemma

I have two questions:

1. I consider the following language $$L_1= \{ w\in \{0,1\}^* \mid \not \exists u\in \{0,1\}^* \colon w= uu^R\}.$$ In other words $w$ is not palindrome with even length. I proved that this language is NOT regular by proving that its complement is not regular. My question is how to prove it using the pumping lemma without using going over the complement.

2. Let $$L_2=\{w\in\{0,1\}^* \mid \text{w has same number of 101 substrings and 010 substrings}\}.$$ I proved that this language is not regular by using equivalence classes. How I can prove it using the pumping lemma?

Thanks alot for edit:)

-
Note. My browser does not show the "not exists" sign in the description of $L_1$. Don't worry: it is there in the source, and changing browsers helped. –  Hendrik Jan Dec 7 '12 at 22:18
@Farseer Pumping Lemma is very essay –  Grijesh Chauhan Dec 8 '12 at 19:03

Not all non-regular languages fail the test of the pumping lemma. Wikipedia has an annoyingly complex example of a non-regular language which can be pumped. So even if a language is non-regular, we may not be able to prove this fact using the pumping lemma.

But it turns out we can use the pumping lemma to prove your first language is not regular. I'm not sure about the second.

Claim: $L_1$ is non-regular.

Proof: By the pumping lemma. Let $p$ be the pumping length. (I'm going to use the alphabet $\{a,b\}$ rather than $\{0,1\}$.) If $p = 1$, then take the string $abbaa$, which is in $L_1$ and pump it to $aabbaa$ which is not in $L_1$, so $L_1$ would not be regular.

If $p > 1$, then take the string $a^pbba^{N}$. (We'll figure out what we want $N$ to be later.) Then consider any division of the string into $xyz$ where $x=a^{p-k}$, $y=a^k$, and $z=bba^{N}$.

Now let's pump this string $i$ times. (We'll figure out what we want $i$ to be later.) We get the string $xy^iz$, which gives $a^{p-k}a^{ik}bba^{N} = a^{p-k+ik}bba^{N}$.

Now let's back up. First, we picked $N$. Then, some choice of $k$ was made. Then, we picked $i$. We want to figure out what $N$ to pick so that, for any choice of $k \in [1,p]$, we can choose an $i$ that makes this string a palindrome by making the number of $a$s on the left equal the number on the right. (It will always have even length.)

So we want to always get that $p-k+ik=N$. If we play around with the math, we find that we should pick $N=p+p!$ and pick $i=p!/k+1$.

So to recap, we picked $N=p+p!$ and chose the string $a^pbba^N$. Then some choice of $k$ was made so that the string was made up of $a^{p-k}ybba^N$ where $y=a^k$. Then we picked $i=p!/k + 1$. We pumped the string to get $a^{p-k}y^{i}bba^N = a^{p-k}a^{ik}bba^N = a^{p-k+ik}bba^N$.

But we know that $p-k+ik = p-k+(\frac{p!}{k}+1)k = p-k+p!+k=p+p!$. And $N=p+p!$. So the number of $a$s on both ends is the same, so the string is an even-length palindrome, so it's not in $L_1$, so $L_1$ is not regular. $\square$

-
Perfect answer! –  farseer Dec 8 '12 at 8:38
Many thanks for help. The idea want to choose string wisely. –  farseer Dec 8 '12 at 8:39
I would have liked to give you an answer to both languages, but the second one looks painful! The approach that led me to the answer on the first one was trying to prove that $L_1$ actually is pumpable -- when I got to the final case and couldn't prove it, I could start to see how to construct the string above. –  usul Dec 8 '12 at 9:11

For question one the string $0^{p}1^{2p}0^{p+p!}$ is a suitable counter-example. What ever the length of $y$ is, it must be a factor of $p!$, so we pump it enough and we get $p+p!$ zeroes at the start.

-

After long thinking i think i answered 2.

we choose string (010)^N(101)^N , where N is pumping length. No matter what y we will choose, xy^0z will have more 101 then 010. the idea is that we can only add more 101 sub strings in first part of string or remove some 010 sub strings.

-
Unfortunately it does not seem to work :( String 010010101101 (N=2) has three(!) occurrences of each. Deleting the third letter, we get 01010101101, which still has three occurrences of 010. Mind the overlap. I am still puzzled... –  Hendrik Jan Dec 8 '12 at 12:08
Yes! But we have 4 occurrences of 101! And so amount of 101 sub strings != amount of 010 –  farseer Dec 8 '12 at 12:29
Oops. Sorry. I should have read what you exactly said: "add more 101 substrings". +1 (case closed) –  Hendrik Jan Dec 8 '12 at 13:01