Mixing
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 2 days ago
Mugumble
402210
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 2 days ago
Mugumble
402210
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
yesterday
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
yesterday
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
yesterday
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 2 days ago
Mugumble
402210
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 2 days ago
Mugumble
402210
asked 2 days ago
Mugumble
402210
edited 2 days ago
asked 2 days ago
Mugumble
402210
asked 2 days ago
Mugumble
402210
asked 2 days ago
Mugumble
402210
402210
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
yesterday
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
yesterday
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
yesterday
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
yesterday
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
yesterday
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
yesterday
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
yesterday
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
yesterday
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
yesterday
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
yesterday
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
yesterday
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
yesterday
add a comment |
active
oldest
votes
active
oldest
votes
active
oldest
votes
active
oldest
votes
active
oldest
votes
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
yesterday
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
yesterday
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
yesterday