Searching for a proof for a variant of the pumping lemma for context free languages
up vote
3
down vote
favorite
So I'm trying to understand the pumping lemma for CFL ( context free languages ).I've already used it to show that a language is not contextfree and I have considered the proof of this lemma (see the PDF below ) Now I've read that there is a variant of the pumping lemma for context free languages. You replace the condition " $ vy neq varepsilon $ " with " $v$ and
$y$ are not $varepsilon$". Like I've said. Here is the proof of the"normal" pumping lemma for CFL.
https://www.google.de/url?sa=t&source=web&rct=j&url=https://cs.uwaterloo.ca/~watrous/CS360.Spring2017/Lectures/10.pdf&ved=2ahUKEwjs_PfAluHeAhWCzKQKHR6BDgwQFjAKegQICRAB&usg=AOvVaw14bQTaIb205pRrv2NpsGGX
What do I have to change for the variant of the pumping lemma?
formal-languages context-free-grammar pumping-lemma
asked Nov 19 at 19:36
Mugumble
447212
add a comment |
up vote
3
down vote
favorite
So I'm trying to understand the pumping lemma for CFL ( context free languages ).I've already used it to show that a language is not contextfree and I have considered the proof of this lemma (see the PDF below ) Now I've read that there is a variant of the pumping lemma for context free languages. You replace the condition " $ vy neq varepsilon $ " with " $v$ and
$y$ are not $varepsilon$". Like I've said. Here is the proof of the"normal" pumping lemma for CFL.
https://www.google.de/url?sa=t&source=web&rct=j&url=https://cs.uwaterloo.ca/~watrous/CS360.Spring2017/Lectures/10.pdf&ved=2ahUKEwjs_PfAluHeAhWCzKQKHR6BDgwQFjAKegQICRAB&usg=AOvVaw14bQTaIb205pRrv2NpsGGX
What do I have to change for the variant of the pumping lemma?
formal-languages context-free-grammar pumping-lemma
asked Nov 19 at 19:36
Mugumble
447212
There are some stronger variants of the pumping lemma like the Ogden Lemma or the Bader-Moura Lemma. Concerning the variant you mention, it can certainly not be proved for the same constant. I even doubt that it is possible at all, already for the simple fact that people would probably use this stronger variant.
– Peter Leupold
Nov 20 at 10:55
However, my first idea was this one: Take a larger constant that guarantees the existence of two non-interleaving loops in the derivation. If one of them produces pump factors on either side, take it for the proof of the lemma as before. If both produce non-terminals only on one side, take these two factors for the pumping. Here not just all $uv^iwx^iy$ are in the language, but all $uv^iwx^ky$; but the latter of course implies the former. So this kind of pumping is maybe not in the original spirit, but it still works.
– Peter Leupold
Nov 20 at 10:56
The constant might be significantly bigger and more complicated to calculate for a given grammar. More importantly, you loose the condition $|vwx|<c$ for the constant c, because the two loops might be far apart. Probably you can guarantee that one loop is below the other - but this makes the calculation of the constant even more complicated.
– Peter Leupold
Nov 20 at 10:57
add a comment |
up vote
3
down vote
favorite
up vote
3
down vote
favorite
So I'm trying to understand the pumping lemma for CFL ( context free languages ).I've already used it to show that a language is not contextfree and I have considered the proof of this lemma (see the PDF below ) Now I've read that there is a variant of the pumping lemma for context free languages. You replace the condition " $ vy neq varepsilon $ " with " $v$ and
$y$ are not $varepsilon$". Like I've said. Here is the proof of the"normal" pumping lemma for CFL.
https://www.google.de/url?sa=t&source=web&rct=j&url=https://cs.uwaterloo.ca/~watrous/CS360.Spring2017/Lectures/10.pdf&ved=2ahUKEwjs_PfAluHeAhWCzKQKHR6BDgwQFjAKegQICRAB&usg=AOvVaw14bQTaIb205pRrv2NpsGGX
What do I have to change for the variant of the pumping lemma?
formal-languages context-free-grammar pumping-lemma
asked Nov 19 at 19:36
Mugumble
447212
So I'm trying to understand the pumping lemma for CFL ( context free languages ).I've already used it to show that a language is not contextfree and I have considered the proof of this lemma (see the PDF below ) Now I've read that there is a variant of the pumping lemma for context free languages. You replace the condition " $ vy neq varepsilon $ " with " $v$ and
$y$ are not $varepsilon$". Like I've said. Here is the proof of the"normal" pumping lemma for CFL.
https://www.google.de/url?sa=t&source=web&rct=j&url=https://cs.uwaterloo.ca/~watrous/CS360.Spring2017/Lectures/10.pdf&ved=2ahUKEwjs_PfAluHeAhWCzKQKHR6BDgwQFjAKegQICRAB&usg=AOvVaw14bQTaIb205pRrv2NpsGGX
What do I have to change for the variant of the pumping lemma?
formal-languages context-free-grammar pumping-lemma
formal-languages context-free-grammar pumping-lemma
asked Nov 19 at 19:36
Mugumble
447212
asked Nov 19 at 19:36
Mugumble
447212
edited Nov 19 at 19:48
asked Nov 19 at 19:36
Mugumble
447212
asked Nov 19 at 19:36
Mugumble
447212
asked Nov 19 at 19:36
Mugumble
447212
447212
There are some stronger variants of the pumping lemma like the Ogden Lemma or the Bader-Moura Lemma. Concerning the variant you mention, it can certainly not be proved for the same constant. I even doubt that it is possible at all, already for the simple fact that people would probably use this stronger variant.
– Peter Leupold
Nov 20 at 10:55
However, my first idea was this one: Take a larger constant that guarantees the existence of two non-interleaving loops in the derivation. If one of them produces pump factors on either side, take it for the proof of the lemma as before. If both produce non-terminals only on one side, take these two factors for the pumping. Here not just all $uv^iwx^iy$ are in the language, but all $uv^iwx^ky$; but the latter of course implies the former. So this kind of pumping is maybe not in the original spirit, but it still works.
– Peter Leupold
Nov 20 at 10:56
The constant might be significantly bigger and more complicated to calculate for a given grammar. More importantly, you loose the condition $|vwx|<c$ for the constant c, because the two loops might be far apart. Probably you can guarantee that one loop is below the other - but this makes the calculation of the constant even more complicated.
– Peter Leupold
Nov 20 at 10:57
add a comment |
There are some stronger variants of the pumping lemma like the Ogden Lemma or the Bader-Moura Lemma. Concerning the variant you mention, it can certainly not be proved for the same constant. I even doubt that it is possible at all, already for the simple fact that people would probably use this stronger variant.
– Peter Leupold
Nov 20 at 10:55
However, my first idea was this one: Take a larger constant that guarantees the existence of two non-interleaving loops in the derivation. If one of them produces pump factors on either side, take it for the proof of the lemma as before. If both produce non-terminals only on one side, take these two factors for the pumping. Here not just all $uv^iwx^iy$ are in the language, but all $uv^iwx^ky$; but the latter of course implies the former. So this kind of pumping is maybe not in the original spirit, but it still works.
– Peter Leupold
Nov 20 at 10:56
The constant might be significantly bigger and more complicated to calculate for a given grammar. More importantly, you loose the condition $|vwx|<c$ for the constant c, because the two loops might be far apart. Probably you can guarantee that one loop is below the other - but this makes the calculation of the constant even more complicated.
– Peter Leupold
Nov 20 at 10:57
There are some stronger variants of the pumping lemma like the Ogden Lemma or the Bader-Moura Lemma. Concerning the variant you mention, it can certainly not be proved for the same constant. I even doubt that it is possible at all, already for the simple fact that people would probably use this stronger variant.
– Peter Leupold
Nov 20 at 10:55
There are some stronger variants of the pumping lemma like the Ogden Lemma or the Bader-Moura Lemma. Concerning the variant you mention, it can certainly not be proved for the same constant. I even doubt that it is possible at all, already for the simple fact that people would probably use this stronger variant.
– Peter Leupold
Nov 20 at 10:55
However, my first idea was this one: Take a larger constant that guarantees the existence of two non-interleaving loops in the derivation. If one of them produces pump factors on either side, take it for the proof of the lemma as before. If both produce non-terminals only on one side, take these two factors for the pumping. Here not just all $uv^iwx^iy$ are in the language, but all $uv^iwx^ky$; but the latter of course implies the former. So this kind of pumping is maybe not in the original spirit, but it still works.
– Peter Leupold
Nov 20 at 10:56
However, my first idea was this one: Take a larger constant that guarantees the existence of two non-interleaving loops in the derivation. If one of them produces pump factors on either side, take it for the proof of the lemma as before. If both produce non-terminals only on one side, take these two factors for the pumping. Here not just all $uv^iwx^iy$ are in the language, but all $uv^iwx^ky$; but the latter of course implies the former. So this kind of pumping is maybe not in the original spirit, but it still works.
– Peter Leupold
Nov 20 at 10:56
The constant might be significantly bigger and more complicated to calculate for a given grammar. More importantly, you loose the condition $|vwx|<c$ for the constant c, because the two loops might be far apart. Probably you can guarantee that one loop is below the other - but this makes the calculation of the constant even more complicated.
– Peter Leupold
Nov 20 at 10:57
The constant might be significantly bigger and more complicated to calculate for a given grammar. More importantly, you loose the condition $|vwx|<c$ for the constant c, because the two loops might be far apart. Probably you can guarantee that one loop is below the other - but this makes the calculation of the constant even more complicated.
– Peter Leupold
Nov 20 at 10:57
add a comment |
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',
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%2f3005411%2fsearching-for-a-proof-for-a-variant-of-the-pumping-lemma-for-context-free-langua%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
active
oldest
votes
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.
Some of your past answers have not been well-received, and you're in danger of being blocked from answering.
Please pay close attention to the following guidance:
- 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.
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%2f3005411%2fsearching-for-a-proof-for-a-variant-of-the-pumping-lemma-for-context-free-langua%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
There are some stronger variants of the pumping lemma like the Ogden Lemma or the Bader-Moura Lemma. Concerning the variant you mention, it can certainly not be proved for the same constant. I even doubt that it is possible at all, already for the simple fact that people would probably use this stronger variant.
– Peter Leupold
Nov 20 at 10:55
However, my first idea was this one: Take a larger constant that guarantees the existence of two non-interleaving loops in the derivation. If one of them produces pump factors on either side, take it for the proof of the lemma as before. If both produce non-terminals only on one side, take these two factors for the pumping. Here not just all $uv^iwx^iy$ are in the language, but all $uv^iwx^ky$; but the latter of course implies the former. So this kind of pumping is maybe not in the original spirit, but it still works.
– Peter Leupold
Nov 20 at 10:56
The constant might be significantly bigger and more complicated to calculate for a given grammar. More importantly, you loose the condition $|vwx|<c$ for the constant c, because the two loops might be far apart. Probably you can guarantee that one loop is below the other - but this makes the calculation of the constant even more complicated.
– Peter Leupold
Nov 20 at 10:57