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

Question

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.

Answer 1

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).