6 replaced http://math.stackexchange.com/ with https://math.stackexchange.com/ edited Apr 13 '17 at 12:19 $$L=\{0^m1^n \enspace | \enspace m \neq n\}$$ I saw that this exact question exists elsewhereelsewhere, 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: Assume $$L$$ is not regular. Let $$p$$ be the pumping length given by the Pumping Lemma for regular languages. Let the string $$w = 0^p1^{p+1} \in L$$ 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}$$. Let: \begin{aligned} \mathcal{x} &= \mathcal{0}^{p} \\ {y} & = {1}^{p+1} \\ {z} & = \varepsilon \end{aligned} 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: We see that $$\lvert y \rvert= p+1 \geq 1 \enspace \color{green}{\checkmark}$$ 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? $$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: Assume $$L$$ is not regular. Let $$p$$ be the pumping length given by the Pumping Lemma for regular languages. Let the string $$w = 0^p1^{p+1} \in L$$ 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}$$. Let: \begin{aligned} \mathcal{x} &= \mathcal{0}^{p} \\ {y} & = {1}^{p+1} \\ {z} & = \varepsilon \end{aligned} 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: We see that $$\lvert y \rvert= p+1 \geq 1 \enspace \color{green}{\checkmark}$$ 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? $$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: Assume $$L$$ is not regular. Let $$p$$ be the pumping length given by the Pumping Lemma for regular languages. Let the string $$w = 0^p1^{p+1} \in L$$ 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}$$. Let: \begin{aligned} \mathcal{x} &= \mathcal{0}^{p} \\ {y} & = {1}^{p+1} \\ {z} & = \varepsilon \end{aligned} 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: We see that $$\lvert y \rvert= p+1 \geq 1 \enspace \color{green}{\checkmark}$$ 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? Post Closed as "unclear what you're asking" by D.W.♦, David Richerby, Juho, Nicholas Mancuso, Shaull occurred May 5 '15 at 18:58 5 added 152 characters in body edited May 3 '15 at 19:12 Chuckles 633 bronze badges $$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: Assume $$L$$ is not regular. Let $$p$$ be the pumping length given by the Pumping Lemma for regular languages. Let the string $$w = 0^p1^{p+1} \in L$$ 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}$$. Let: \begin{aligned} \mathcal{x} &= \mathcal{0}^{p} \\ {y} & = {1}^{p+1} \\ {z} & = \varepsilon \end{aligned} 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: We see that $$\lvert y \rvert= p+1 \geq 1 \enspace \color{green}{\checkmark}$$ 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? $$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: Assume $$L$$ is not regular. Let $$p$$ be the pumping length given by the Pumping Lemma for regular languages. Let the string $$w = 0^p1^{p+1} \in L$$ 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}$$. Let: \begin{aligned} \mathcal{x} &= \mathcal{0}^{p} \\ {y} & = {1}^{p+1} \\ {z} & = \varepsilon \end{aligned} 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: We see that $$\lvert y \rvert= p+1 \geq 1 \enspace \color{green}{\checkmark}$$ 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? $$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: Assume $$L$$ is not regular. Let $$p$$ be the pumping length given by the Pumping Lemma for regular languages. Let the string $$w = 0^p1^{p+1} \in L$$ 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}$$. Let: \begin{aligned} \mathcal{x} &= \mathcal{0}^{p} \\ {y} & = {1}^{p+1} \\ {z} & = \varepsilon \end{aligned} 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: We see that $$\lvert y \rvert= p+1 \geq 1 \enspace \color{green}{\checkmark}$$ 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? 4 edited tags | link edited May 3 '15 at 9:59 Raphael♦ 59k2525 gold badges144144 silver badges327327 bronze badges 3 added 28 characters in body edited May 2 '15 at 19:55 Chuckles 633 bronze badges 2 added 28 characters in body edited May 2 '15 at 19:40 Chuckles 633 bronze badges 1 asked May 2 '15 at 19:15 Chuckles 633 bronze badges