Mixing
Pumping Lemma for regular languages proof template
$begingroup$
http://www.cs.uiuc.edu/class/fa06/cs273/Lectures/pumping-lemma/pumping-lemma.html
So, I went to that site and it says:
- $w = xyz$
- $|xy| leq p$
- $|y| geq 1$
- for all $i$, $xy^iz$ is in $L$.
There exists a string $w^p$ in $L$ of length at least $p$ such that if we choose any strings $x$,$y$,and $z$ satisfying conditions (1)-(3), then there is some number $i$ such that $xy^iz$ is not in $L$.
So, we can choose the values for $x$, $y$ and $z$, and we get to choose the $i$ in $xy^iz$, but not $p$, which remains $p$, right?
How do we choose a good string for the pumping lemma?
I asked a question and one of the guy said:
Mr. Pumping Lemma divides $s$ into three parts $u,v,w$, subject to the restrictions that $|uv|≤p$, $|v|≥1$.
which implies I cannot choose a particular value of $x$, $y$ and $z$, but that's not the case, right?
I only have to make sure that $i$ is an integer, amongst other things. What are those other things?
Also, I have another question: there is a case where we have to cover several cases. Like there may be a case where y can take different values and we have to prove that for every case there is a contradiction if I remember well. When does that happen?
automata regular-language
edited Apr 13 '17 at 12:20
Community♦
1
asked Feb 19 '14 at 15:44
user539484user539484
165111
$endgroup$
add a comment |
$begingroup$
http://www.cs.uiuc.edu/class/fa06/cs273/Lectures/pumping-lemma/pumping-lemma.html
So, I went to that site and it says:
- $w = xyz$
- $|xy| leq p$
- $|y| geq 1$
- for all $i$, $xy^iz$ is in $L$.
There exists a string $w^p$ in $L$ of length at least $p$ such that if we choose any strings $x$,$y$,and $z$ satisfying conditions (1)-(3), then there is some number $i$ such that $xy^iz$ is not in $L$.
So, we can choose the values for $x$, $y$ and $z$, and we get to choose the $i$ in $xy^iz$, but not $p$, which remains $p$, right?
How do we choose a good string for the pumping lemma?
I asked a question and one of the guy said:
Mr. Pumping Lemma divides $s$ into three parts $u,v,w$, subject to the restrictions that $|uv|≤p$, $|v|≥1$.
which implies I cannot choose a particular value of $x$, $y$ and $z$, but that's not the case, right?
I only have to make sure that $i$ is an integer, amongst other things. What are those other things?
Also, I have another question: there is a case where we have to cover several cases. Like there may be a case where y can take different values and we have to prove that for every case there is a contradiction if I remember well. When does that happen?
automata regular-language
edited Apr 13 '17 at 12:20
Community♦
1
asked Feb 19 '14 at 15:44
user539484user539484
165111
$endgroup$
$begingroup$
The site you're linking to misses a constraint. It must also be $|w|geq p$.
$endgroup$
– frabala
Feb 21 '14 at 15:30
add a comment |
$begingroup$
http://www.cs.uiuc.edu/class/fa06/cs273/Lectures/pumping-lemma/pumping-lemma.html
So, I went to that site and it says:
- $w = xyz$
- $|xy| leq p$
- $|y| geq 1$
- for all $i$, $xy^iz$ is in $L$.
There exists a string $w^p$ in $L$ of length at least $p$ such that if we choose any strings $x$,$y$,and $z$ satisfying conditions (1)-(3), then there is some number $i$ such that $xy^iz$ is not in $L$.
So, we can choose the values for $x$, $y$ and $z$, and we get to choose the $i$ in $xy^iz$, but not $p$, which remains $p$, right?
How do we choose a good string for the pumping lemma?
I asked a question and one of the guy said:
Mr. Pumping Lemma divides $s$ into three parts $u,v,w$, subject to the restrictions that $|uv|≤p$, $|v|≥1$.
which implies I cannot choose a particular value of $x$, $y$ and $z$, but that's not the case, right?
I only have to make sure that $i$ is an integer, amongst other things. What are those other things?
Also, I have another question: there is a case where we have to cover several cases. Like there may be a case where y can take different values and we have to prove that for every case there is a contradiction if I remember well. When does that happen?
automata regular-language
edited Apr 13 '17 at 12:20
Community♦
1
asked Feb 19 '14 at 15:44
user539484user539484
165111
$endgroup$
http://www.cs.uiuc.edu/class/fa06/cs273/Lectures/pumping-lemma/pumping-lemma.html
So, I went to that site and it says:
- $w = xyz$
- $|xy| leq p$
- $|y| geq 1$
- for all $i$, $xy^iz$ is in $L$.
There exists a string $w^p$ in $L$ of length at least $p$ such that if we choose any strings $x$,$y$,and $z$ satisfying conditions (1)-(3), then there is some number $i$ such that $xy^iz$ is not in $L$.
So, we can choose the values for $x$, $y$ and $z$, and we get to choose the $i$ in $xy^iz$, but not $p$, which remains $p$, right?
How do we choose a good string for the pumping lemma?
I asked a question and one of the guy said:
Mr. Pumping Lemma divides $s$ into three parts $u,v,w$, subject to the restrictions that $|uv|≤p$, $|v|≥1$.
which implies I cannot choose a particular value of $x$, $y$ and $z$, but that's not the case, right?
I only have to make sure that $i$ is an integer, amongst other things. What are those other things?
Also, I have another question: there is a case where we have to cover several cases. Like there may be a case where y can take different values and we have to prove that for every case there is a contradiction if I remember well. When does that happen?
automata regular-language
automata regular-language
edited Apr 13 '17 at 12:20
Community♦
1
asked Feb 19 '14 at 15:44
user539484user539484
165111
edited Apr 13 '17 at 12:20
Community♦
1
asked Feb 19 '14 at 15:44
user539484user539484
165111
edited Apr 13 '17 at 12:20
Community♦
1
edited Apr 13 '17 at 12:20
Community♦
1
edited Apr 13 '17 at 12:20
Community♦
1
1
asked Feb 19 '14 at 15:44
user539484user539484
165111
asked Feb 19 '14 at 15:44
user539484user539484
165111
asked Feb 19 '14 at 15:44
user539484user539484
165111
165111
$begingroup$
The site you're linking to misses a constraint. It must also be $|w|geq p$.
$endgroup$
– frabala
Feb 21 '14 at 15:30
add a comment |
$begingroup$
The site you're linking to misses a constraint. It must also be $|w|geq p$.
$endgroup$
– frabala
Feb 21 '14 at 15:30
$begingroup$
The site you're linking to misses a constraint. It must also be $|w|geq p$.
$endgroup$
– frabala
Feb 21 '14 at 15:30
$begingroup$
The site you're linking to misses a constraint. It must also be $|w|geq p$.
$endgroup$
– frabala
Feb 21 '14 at 15:30
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
My professor, when teaching us the pumping lemma for the first time, he introduced it as a game between two people. The goal for you is to prove that a language is not regular.
Step 1: You choose some $pinmathbb{Z}$. So, $p$ is already an integer. You don't have to show this. It is by assumption.
Step 2: Your opponent chooses some $win L$, with $|w|geq p$.
Step 3: You choose some $x,y$ and $z$ such, that $w=xyz$ with the constraints $|xy|<p$ and $|y|geq 1$. Here is were you might need to take cases for the $x,y$ and $z$ that you have to choose.
Step 4: For each case from step 3, you find some $i$, such that $xy^iznotin L$.
You win if you manage until step 4. The opponent wins if you don't.
Of course, when applying the pumping lemma to prove that a language is not regular, you don't actually play this game with another person. You get to do the roles of yourself and of your opponent. You can think of it like you're having identity disorders (here we laugh) and the two personalities are your opponent and yourself.
So, basically, what you have to find is $p$, $x,y,z$ and $i$. But most of the times it is convenient to keep $p$ as a fixed variable and not give it some value. In this case, you choose $p$ by saying "let $pinmathbb{Z}$" and move on as if $p$ is a non-negative integer. So actually, what you need to find are $x, y, z$ and $i$, for given $w$.
answered Feb 21 '14 at 12:52
frabalafrabala
2,5341122
$endgroup$
add a comment |
Your Answer
StackExchange.ifUsing("editor", function () {
return StackExchange.using("mathjaxEditing", function () {
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
});
});
}, "mathjax-editing");
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "69"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});
function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f682242%2fpumping-lemma-for-regular-languages-proof-template%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
My professor, when teaching us the pumping lemma for the first time, he introduced it as a game between two people. The goal for you is to prove that a language is not regular.
Step 1: You choose some $pinmathbb{Z}$. So, $p$ is already an integer. You don't have to show this. It is by assumption.
Step 2: Your opponent chooses some $win L$, with $|w|geq p$.
Step 3: You choose some $x,y$ and $z$ such, that $w=xyz$ with the constraints $|xy|<p$ and $|y|geq 1$. Here is were you might need to take cases for the $x,y$ and $z$ that you have to choose.
Step 4: For each case from step 3, you find some $i$, such that $xy^iznotin L$.
You win if you manage until step 4. The opponent wins if you don't.
Of course, when applying the pumping lemma to prove that a language is not regular, you don't actually play this game with another person. You get to do the roles of yourself and of your opponent. You can think of it like you're having identity disorders (here we laugh) and the two personalities are your opponent and yourself.
So, basically, what you have to find is $p$, $x,y,z$ and $i$. But most of the times it is convenient to keep $p$ as a fixed variable and not give it some value. In this case, you choose $p$ by saying "let $pinmathbb{Z}$" and move on as if $p$ is a non-negative integer. So actually, what you need to find are $x, y, z$ and $i$, for given $w$.
answered Feb 21 '14 at 12:52
frabalafrabala
2,5341122
$endgroup$
add a comment |
$begingroup$
My professor, when teaching us the pumping lemma for the first time, he introduced it as a game between two people. The goal for you is to prove that a language is not regular.
Step 1: You choose some $pinmathbb{Z}$. So, $p$ is already an integer. You don't have to show this. It is by assumption.
Step 2: Your opponent chooses some $win L$, with $|w|geq p$.
Step 3: You choose some $x,y$ and $z$ such, that $w=xyz$ with the constraints $|xy|<p$ and $|y|geq 1$. Here is were you might need to take cases for the $x,y$ and $z$ that you have to choose.
Step 4: For each case from step 3, you find some $i$, such that $xy^iznotin L$.
You win if you manage until step 4. The opponent wins if you don't.
Of course, when applying the pumping lemma to prove that a language is not regular, you don't actually play this game with another person. You get to do the roles of yourself and of your opponent. You can think of it like you're having identity disorders (here we laugh) and the two personalities are your opponent and yourself.
So, basically, what you have to find is $p$, $x,y,z$ and $i$. But most of the times it is convenient to keep $p$ as a fixed variable and not give it some value. In this case, you choose $p$ by saying "let $pinmathbb{Z}$" and move on as if $p$ is a non-negative integer. So actually, what you need to find are $x, y, z$ and $i$, for given $w$.
answered Feb 21 '14 at 12:52
frabalafrabala
2,5341122
$endgroup$
add a comment |
$begingroup$
My professor, when teaching us the pumping lemma for the first time, he introduced it as a game between two people. The goal for you is to prove that a language is not regular.
Step 1: You choose some $pinmathbb{Z}$. So, $p$ is already an integer. You don't have to show this. It is by assumption.
Step 2: Your opponent chooses some $win L$, with $|w|geq p$.
Step 3: You choose some $x,y$ and $z$ such, that $w=xyz$ with the constraints $|xy|<p$ and $|y|geq 1$. Here is were you might need to take cases for the $x,y$ and $z$ that you have to choose.
Step 4: For each case from step 3, you find some $i$, such that $xy^iznotin L$.
You win if you manage until step 4. The opponent wins if you don't.
Of course, when applying the pumping lemma to prove that a language is not regular, you don't actually play this game with another person. You get to do the roles of yourself and of your opponent. You can think of it like you're having identity disorders (here we laugh) and the two personalities are your opponent and yourself.
So, basically, what you have to find is $p$, $x,y,z$ and $i$. But most of the times it is convenient to keep $p$ as a fixed variable and not give it some value. In this case, you choose $p$ by saying "let $pinmathbb{Z}$" and move on as if $p$ is a non-negative integer. So actually, what you need to find are $x, y, z$ and $i$, for given $w$.
answered Feb 21 '14 at 12:52
frabalafrabala
2,5341122
$endgroup$
My professor, when teaching us the pumping lemma for the first time, he introduced it as a game between two people. The goal for you is to prove that a language is not regular.
Step 1: You choose some $pinmathbb{Z}$. So, $p$ is already an integer. You don't have to show this. It is by assumption.
Step 2: Your opponent chooses some $win L$, with $|w|geq p$.
Step 3: You choose some $x,y$ and $z$ such, that $w=xyz$ with the constraints $|xy|<p$ and $|y|geq 1$. Here is were you might need to take cases for the $x,y$ and $z$ that you have to choose.
Step 4: For each case from step 3, you find some $i$, such that $xy^iznotin L$.
You win if you manage until step 4. The opponent wins if you don't.
Of course, when applying the pumping lemma to prove that a language is not regular, you don't actually play this game with another person. You get to do the roles of yourself and of your opponent. You can think of it like you're having identity disorders (here we laugh) and the two personalities are your opponent and yourself.
So, basically, what you have to find is $p$, $x,y,z$ and $i$. But most of the times it is convenient to keep $p$ as a fixed variable and not give it some value. In this case, you choose $p$ by saying "let $pinmathbb{Z}$" and move on as if $p$ is a non-negative integer. So actually, what you need to find are $x, y, z$ and $i$, for given $w$.
answered Feb 21 '14 at 12:52
frabalafrabala
2,5341122
edited Feb 21 '14 at 13:39
answered Feb 21 '14 at 12:52
frabalafrabala
2,5341122
answered Feb 21 '14 at 12:52
frabalafrabala
2,5341122
answered Feb 21 '14 at 12:52
frabalafrabala
2,5341122
2,5341122
add a comment |
add a comment |
Thanks for contributing an answer to Mathematics Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f682242%2fpumping-lemma-for-regular-languages-proof-template%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
$begingroup$
The site you're linking to misses a constraint. It must also be $|w|geq p$.
$endgroup$
– frabala
Feb 21 '14 at 15:30