0
$\begingroup$

$$L=\{0^m1^n \enspace | \enspace m \neq n\}$$

I saw that this exact question exists elsewhere, but I couldn't understand what was being said there. My question does not mandate the use of the Pumping Lemma as stated "elsewhere", but I am using the Pumping Lemma anyway. I want to present what I have so far, and for someone to tell me if I'm on the right track:

  1. Assume $L$ is not regular.
  2. Let $p$ be the pumping length given by the Pumping Lemma for regular languages.
  3. Let the string $w = 0^p1^{p+1} \in L$
  4. By the Pumping Lemma, $w = xy^iz$, where $i \geq 0$, $\color{green}{\lvert y \rvert \geq 1}$, and $\color{red}{\lvert xy \rvert \lt p}$.
  5. Let:

\begin{equation} \begin{aligned} \mathcal{x} &= \mathcal{0}^{p} \\ {y} & = {1}^{p+1} \\ {z} & = \varepsilon \end{aligned} \end{equation}

It is at this point in the proof that I get confused. I feel as if I've set it up well, but just can't finish. Here's what I've got, though:

  1. We see that $\lvert y \rvert= p+1 \geq 1 \enspace \color{green}{\checkmark}$
  2. However, $\lvert xy \rvert= p+p+1 \gt p \enspace \color{red}{\textbf{X}}$

As we can see by $\textit{(7)}$, our test string $w$ violates a $\color{red}{condition}$ of the Pumping Lemma, thus is not regular.

Thumbs up, thumbs down, anyone? Did I make the appropriate inferences about my split string $w$ in order to achieve a contradiction, and did I even split the string correctly? And to boot, did I even pick a $w$ that is useful to the proof?

$\endgroup$

closed as unclear what you're asking by D.W., David Richerby, Juho, Nicholas Mancuso, Shaull May 5 '15 at 18:58

Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.

  • 1
    $\begingroup$ Your question already includes a complete answer to the original problem but no question about this answer. Thus, only "yes/no" answers may remain, helping neither you nor future visitors. Please read related meta discussions here and here and adjust your question accordingly, e.g. by formulating a specific question about a single element of your answer you are uncertain about. This kind of question isn't an optimal fit for this site, as it's not likely to be helpful to others in the future. $\endgroup$ – D.W. May 3 '15 at 0:15
  • $\begingroup$ Thanks for the tips, I am a bit new to Stack Exchange. However, I stand by my question's structure. I specifically refer to when I said, "I feel as if I've set it up well, but just can't finish." I think this is a pretty clear statement that points to a specific point of confusion in my proof. Yes, I do end the post with "thumbs up, thumbs down," but I believe that my ending statement does not represent the full depth of my question. That being said, I made an edit to add a question that is hopefully much more explicit. I'll try to make specifics a priority in future questions! $\endgroup$ – Chuckles May 3 '15 at 19:10
4
$\begingroup$

This is a very hard one to prove via the pumping lemma, as you have to construct a string that eventually gives you something of the form $0^{n}1^{n}$ for some $n$ when you pump it the right number of times. As Renato notes, your decomposition (at the time of writing this answer) is incorrect. We'll come back to this.

A simpler way is to use the closure properties of regular languages. In particular, regular languages are closed under complementation and intersection, so

  1. If $R$ is regular, then $\overline{R} = \Sigma^{\ast}\setminus R$ is also regular.
  2. If $R_{1}$ and $R_{2}$ are regular, then $R_{3} = R_{1} \cap R_{2}$ is also regular.

So we assume that $L = \{0^{m}1^{n} \mid m \neq n\}$ is regular. Then by (1), $\overline{L} = \Sigma^{\ast}\setminus L$ is regular. In particular note that $\overline{L}$ includes all strings of the form $0^{n}1^{n}$.

The language $A = \{0^{a}1^{b} \mid a,b \in \mathbb{N}\}$ is regular (we can show this via a regular expression, DFA or regular grammar for the language, e.g. $0^{\ast}1^{\ast}$).

Then by (2) $\overline{L}\cap A$ must also be regular, but this is the language $\{0^{n}1^{n}\}$, which is not regular (and much easier to prove via the pumping lemma!).

As noted in the question you linked however, it is possible to do it with the pumping lemma, but you need to pick your starting string carefully. As we only have two sections to the string, the obvious approach is to have a string of the form $0^{p}1^{x}$ for some $x$, so then we know that $y = 0^{k}$ for some $k\leq p$. Now the trick is to pick $x$ such that we can pump the string some number $y$ times and get $p + (y-1)\cdot k = x$. Of course we don't know what $k$ is - it could be anything from $1$ to $p$, so $x$ needs to take this into account. Hence $x$, in part, needs to (almost) be a multiple of every number from $1$ to $p$. So if we pick $x = p + p!$, we can say that for every $k$, there exists a $y$ such that $p + (y-1)\cdot k = p + p!$. In particular $y = \frac{p!}{k}+1$.

So then our starting string is $s=0^{p}1^{p+p!}$. By the pumping lemma if $L$ is regular, we can break $s$ up in $xyz$ such that $|y| \geq 1$, $|xy| \leq p$ and $xy^{i}z \in L$ for every $i \in \mathbb{N}$, but we have just shown that for $i = \frac{p!}{k}+1$, we get the string $0^{p+p!}1^{p+p!} \notin L$. Hence $L$ violates the pumping lemma, can thus can't be regular.

$\endgroup$
  • 2
    $\begingroup$ It is also easy (and intuitive!) to prove that the language is not regular using the Myhill–Nerode criterion: the words $0^n$ are pairwise inequivalent. $\endgroup$ – Yuval Filmus May 3 '15 at 4:00
2
$\begingroup$

Thumbs down because your decomposition is wrong. Pumping lemma complies only if you choose a valid decomposition ($|xy|\leq p$ and $|y|\geq 1$). The idea is that you prove that there are no possible(valid) decompositions such that the pumping lemma is fulfilled

$\endgroup$

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