Why is this choice of $y$ not permitted in using pumping lemma?
$begingroup$
Consider this snippet shown below from, An Introduction to Formal Languages and Automata 6th Edition
by Peter Linz.
As per the text, choosing a value of $y = a^k$, where $k$ is odd is not permitted since this violates the condition of pumping lemma. This text simply says that the assumption on $k$ (number of $a$'s in $y$ being odd) is not permitted.
Now, as far as my understanding goes, the condition on choosing $xy$ is $|xy| le p$, where $p$ is the pumping length, and $|y|>1$. And if we can show that one valid choice of $y$ satisfies the pumping lemma, we have been able to show that this language does not violate the pumping lemma, though the language can not be claimed to be regular. When I need to show that the language is not regular, I need to explore all possible $y$'s.
I fail to understand, why a $y$, with odd number of $a$'s, and $|y| le p$, $x=epsilon$, will not be permitted here.
pumping-lemma
asked Dec 5 '18 at 8:45
MasroorMasroor
80231228
$endgroup$
|
show 3 more comments
$begingroup$
Consider this snippet shown below from, An Introduction to Formal Languages and Automata 6th Edition
by Peter Linz.
As per the text, choosing a value of $y = a^k$, where $k$ is odd is not permitted since this violates the condition of pumping lemma. This text simply says that the assumption on $k$ (number of $a$'s in $y$ being odd) is not permitted.
Now, as far as my understanding goes, the condition on choosing $xy$ is $|xy| le p$, where $p$ is the pumping length, and $|y|>1$. And if we can show that one valid choice of $y$ satisfies the pumping lemma, we have been able to show that this language does not violate the pumping lemma, though the language can not be claimed to be regular. When I need to show that the language is not regular, I need to explore all possible $y$'s.
I fail to understand, why a $y$, with odd number of $a$'s, and $|y| le p$, $x=epsilon$, will not be permitted here.
pumping-lemma
asked Dec 5 '18 at 8:45
MasroorMasroor
80231228
$endgroup$
$begingroup$
If you are using the pumping lemma to prove $L$ is not regular then you are not permitted to make the assumption that $y$ has odd length, or any other assumption of this kind. It is not clear what you want to achieve.
$endgroup$
– Michal Adamaszek
Dec 5 '18 at 9:05
$begingroup$
@MichalAdamaszek Would you mind elaborating, "any other assumption of this kind", part?
$endgroup$
– Masroor
Dec 5 '18 at 9:15
$begingroup$
I mean anything that is not in the conclusion of the pumping lemma.
$endgroup$
– Michal Adamaszek
Dec 5 '18 at 9:24
$begingroup$
@MichalAdamaszek Do you want to put a reference in support of your claim? As far as my understanding goes, if I take $y$ to be of odd length, it does not violate the acceptable conditions for $y$.
$endgroup$
– Masroor
Dec 5 '18 at 9:39
$begingroup$
What do you mean by "you take y"? You get y from the pumping lemma, and not choose it yourself. I am referring to how you use the pumping lemma to prove a language is not regular. Are you trying to do something else?
$endgroup$
– Michal Adamaszek
Dec 5 '18 at 9:56
|
show 3 more comments
$begingroup$
Consider this snippet shown below from, An Introduction to Formal Languages and Automata 6th Edition
by Peter Linz.
As per the text, choosing a value of $y = a^k$, where $k$ is odd is not permitted since this violates the condition of pumping lemma. This text simply says that the assumption on $k$ (number of $a$'s in $y$ being odd) is not permitted.
Now, as far as my understanding goes, the condition on choosing $xy$ is $|xy| le p$, where $p$ is the pumping length, and $|y|>1$. And if we can show that one valid choice of $y$ satisfies the pumping lemma, we have been able to show that this language does not violate the pumping lemma, though the language can not be claimed to be regular. When I need to show that the language is not regular, I need to explore all possible $y$'s.
I fail to understand, why a $y$, with odd number of $a$'s, and $|y| le p$, $x=epsilon$, will not be permitted here.
pumping-lemma
asked Dec 5 '18 at 8:45
MasroorMasroor
80231228
$endgroup$
Consider this snippet shown below from, An Introduction to Formal Languages and Automata 6th Edition
by Peter Linz.
As per the text, choosing a value of $y = a^k$, where $k$ is odd is not permitted since this violates the condition of pumping lemma. This text simply says that the assumption on $k$ (number of $a$'s in $y$ being odd) is not permitted.
Now, as far as my understanding goes, the condition on choosing $xy$ is $|xy| le p$, where $p$ is the pumping length, and $|y|>1$. And if we can show that one valid choice of $y$ satisfies the pumping lemma, we have been able to show that this language does not violate the pumping lemma, though the language can not be claimed to be regular. When I need to show that the language is not regular, I need to explore all possible $y$'s.
I fail to understand, why a $y$, with odd number of $a$'s, and $|y| le p$, $x=epsilon$, will not be permitted here.
pumping-lemma
pumping-lemma
asked Dec 5 '18 at 8:45
MasroorMasroor
80231228
asked Dec 5 '18 at 8:45
MasroorMasroor
80231228
asked Dec 5 '18 at 8:45
MasroorMasroor
80231228
asked Dec 5 '18 at 8:45
MasroorMasroor
80231228
asked Dec 5 '18 at 8:45
MasroorMasroor
80231228
80231228
$begingroup$
If you are using the pumping lemma to prove $L$ is not regular then you are not permitted to make the assumption that $y$ has odd length, or any other assumption of this kind. It is not clear what you want to achieve.
$endgroup$
– Michal Adamaszek
Dec 5 '18 at 9:05
$begingroup$
@MichalAdamaszek Would you mind elaborating, "any other assumption of this kind", part?
$endgroup$
– Masroor
Dec 5 '18 at 9:15
$begingroup$
I mean anything that is not in the conclusion of the pumping lemma.
$endgroup$
– Michal Adamaszek
Dec 5 '18 at 9:24
$begingroup$
@MichalAdamaszek Do you want to put a reference in support of your claim? As far as my understanding goes, if I take $y$ to be of odd length, it does not violate the acceptable conditions for $y$.
$endgroup$
– Masroor
Dec 5 '18 at 9:39
$begingroup$
What do you mean by "you take y"? You get y from the pumping lemma, and not choose it yourself. I am referring to how you use the pumping lemma to prove a language is not regular. Are you trying to do something else?
$endgroup$
– Michal Adamaszek
Dec 5 '18 at 9:56
|
show 3 more comments
$begingroup$
If you are using the pumping lemma to prove $L$ is not regular then you are not permitted to make the assumption that $y$ has odd length, or any other assumption of this kind. It is not clear what you want to achieve.
$endgroup$
– Michal Adamaszek
Dec 5 '18 at 9:05
$begingroup$
@MichalAdamaszek Would you mind elaborating, "any other assumption of this kind", part?
$endgroup$
– Masroor
Dec 5 '18 at 9:15
$begingroup$
I mean anything that is not in the conclusion of the pumping lemma.
$endgroup$
– Michal Adamaszek
Dec 5 '18 at 9:24
$begingroup$
@MichalAdamaszek Do you want to put a reference in support of your claim? As far as my understanding goes, if I take $y$ to be of odd length, it does not violate the acceptable conditions for $y$.
$endgroup$
– Masroor
Dec 5 '18 at 9:39
$begingroup$
What do you mean by "you take y"? You get y from the pumping lemma, and not choose it yourself. I am referring to how you use the pumping lemma to prove a language is not regular. Are you trying to do something else?
$endgroup$
– Michal Adamaszek
Dec 5 '18 at 9:56
$begingroup$
If you are using the pumping lemma to prove $L$ is not regular then you are not permitted to make the assumption that $y$ has odd length, or any other assumption of this kind. It is not clear what you want to achieve.
$endgroup$
– Michal Adamaszek
Dec 5 '18 at 9:05
$begingroup$
If you are using the pumping lemma to prove $L$ is not regular then you are not permitted to make the assumption that $y$ has odd length, or any other assumption of this kind. It is not clear what you want to achieve.
$endgroup$
– Michal Adamaszek
Dec 5 '18 at 9:05
$begingroup$
@MichalAdamaszek Would you mind elaborating, "any other assumption of this kind", part?
$endgroup$
– Masroor
Dec 5 '18 at 9:15
$begingroup$
@MichalAdamaszek Would you mind elaborating, "any other assumption of this kind", part?
$endgroup$
– Masroor
Dec 5 '18 at 9:15
$begingroup$
I mean anything that is not in the conclusion of the pumping lemma.
$endgroup$
– Michal Adamaszek
Dec 5 '18 at 9:24
$begingroup$
I mean anything that is not in the conclusion of the pumping lemma.
$endgroup$
– Michal Adamaszek
Dec 5 '18 at 9:24
$begingroup$
@MichalAdamaszek Do you want to put a reference in support of your claim? As far as my understanding goes, if I take $y$ to be of odd length, it does not violate the acceptable conditions for $y$.
$endgroup$
– Masroor
Dec 5 '18 at 9:39
$begingroup$
@MichalAdamaszek Do you want to put a reference in support of your claim? As far as my understanding goes, if I take $y$ to be of odd length, it does not violate the acceptable conditions for $y$.
$endgroup$
– Masroor
Dec 5 '18 at 9:39
$begingroup$
What do you mean by "you take y"? You get y from the pumping lemma, and not choose it yourself. I am referring to how you use the pumping lemma to prove a language is not regular. Are you trying to do something else?
$endgroup$
– Michal Adamaszek
Dec 5 '18 at 9:56
$begingroup$
What do you mean by "you take y"? You get y from the pumping lemma, and not choose it yourself. I am referring to how you use the pumping lemma to prove a language is not regular. Are you trying to do something else?
$endgroup$
– Michal Adamaszek
Dec 5 '18 at 9:56
|
show 3 more comments
0
active
oldest
votes
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%2f3026818%2fwhy-is-this-choice-of-y-not-permitted-in-using-pumping-lemma%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
0
active
oldest
votes
0
active
oldest
votes
active
oldest
votes
active
oldest
votes
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%2f3026818%2fwhy-is-this-choice-of-y-not-permitted-in-using-pumping-lemma%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$
If you are using the pumping lemma to prove $L$ is not regular then you are not permitted to make the assumption that $y$ has odd length, or any other assumption of this kind. It is not clear what you want to achieve.
$endgroup$
– Michal Adamaszek
Dec 5 '18 at 9:05
$begingroup$
@MichalAdamaszek Would you mind elaborating, "any other assumption of this kind", part?
$endgroup$
– Masroor
Dec 5 '18 at 9:15
$begingroup$
I mean anything that is not in the conclusion of the pumping lemma.
$endgroup$
– Michal Adamaszek
Dec 5 '18 at 9:24
$begingroup$
@MichalAdamaszek Do you want to put a reference in support of your claim? As far as my understanding goes, if I take $y$ to be of odd length, it does not violate the acceptable conditions for $y$.
$endgroup$
– Masroor
Dec 5 '18 at 9:39
$begingroup$
What do you mean by "you take y"? You get y from the pumping lemma, and not choose it yourself. I am referring to how you use the pumping lemma to prove a language is not regular. Are you trying to do something else?
$endgroup$
– Michal Adamaszek
Dec 5 '18 at 9:56