1
$\begingroup$

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.

$\endgroup$
0
1
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ 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? $\endgroup$ – Tatiana Dec 29 '16 at 21:20
  • $\begingroup$ 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. $\endgroup$ – David Richerby Dec 29 '16 at 21:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.