# Pumping lemma for $\{110^n10^{n-m}1^m: 1\le m<n\}$

How can I prove that the language $L=\{110^n 10^{n-m} 1^m \mid 1 \le m < n \}$ is not regular using pumping lemma?

I chose the word $w = 110^{2p} 10^{2p-q} 1^q$ to prove the non-regularity. Then I started partitioning the word to $xyz$ with $|y| \ge 1$, $|xy| \le p$ and for each $i\ge 0$, $xy^iz$:

\begin{align*} x &= 110^r\\ y &= 0^s\\ z &= 10^{2p - q} 1^q\,, \end{align*} where $r + s = p$ and $s > 0$.

The second partition: \begin{align*} x &= 1\\ y &= 10^{2p}\\ z &= 10^{2p-q}1^q\,. \end{align*}

However, I got stuck at this point because I am not really sure how to find the other partitions and how the choose the correct $i$ for those which I already have. Any help with this will be appreciated.

You're basically there. Taking $w=110^{2p}10^{2p−q}1^q$, there are actually three cases (you missed the first one).

1. $x=\varepsilon$, $y=110^{p-2}$, $z=0^{p+2}10^{2p-q}1^q$.

2. $x=1$, $y=10^{p-1}$, $z=0^{p+1}10^{2p-q}1^q$.

3. $x=110^r$ for some $r\in\{0, \dots, p-3\}$, $y=0^{p-r-2}$, $z=0^{p+r+2}10^{2p-q}1^q$.

In all three cases, taking $i=0$ means that the string $xy^iz$ is not in $L$. I'd suggest trying $i=0$ and $i=2$ as your first two guesses in pumping lemma proofs – one of them usually works.

Notice that nothing above actually depends on the choice of $q$, so you can simplify things very slightly by just taking $q=1$ (or any other fixed, legal value).

• Thank you for your answer. Basically, what is important is to split the first 0 into x, y, and z and cover all the possibilities with the first and second 1 -> meaning there's no 1 (just empty string), then there's just one 1 and then there's two with 0^r -> is this the right approach? Also, one more question, what is the general method when choosing the specific word and the partitions? – Tatiana Dec 29 '16 at 21:20
• That's the right approach, yes. There's no general method for choosing the string -- mathematical proof is a creative undertaking and this is where you have to use your creativity. As for the partitions, you need to check that every legal partition of your word as $xyz$ works. – David Richerby Dec 29 '16 at 21:46