Pumping lemma for CFL
up vote
1
down vote
favorite
Q:
Show that L=ww is not context free
My solution:
Assume L is context free
Let its pumping length be P
thus,
string = 0^P 1^P 0^P 1^P
let P=2,
S= 00 11 00 11
S can be divided as u v^i x y^i z
0 0 110 0 11
u v x y z
after pumping,
0 00 110 00 11
u v x y z
0^3 1^2 0^3 1^2
therefore its takes the form of ww ( first condition met)
|vy|=4>0
(second condition met)
|vxy|= 7 which is greater than pumping length 2
(3rd condition is not met)
Therefore, contradicts assumption that L is context free.
Thus L is not context free
Is my proof correct?
computer-science automata language-theory computer-science-theory
add a comment |
up vote
1
down vote
favorite
Q:
Show that L=ww is not context free
My solution:
Assume L is context free
Let its pumping length be P
thus,
string = 0^P 1^P 0^P 1^P
let P=2,
S= 00 11 00 11
S can be divided as u v^i x y^i z
0 0 110 0 11
u v x y z
after pumping,
0 00 110 00 11
u v x y z
0^3 1^2 0^3 1^2
therefore its takes the form of ww ( first condition met)
|vy|=4>0
(second condition met)
|vxy|= 7 which is greater than pumping length 2
(3rd condition is not met)
Therefore, contradicts assumption that L is context free.
Thus L is not context free
Is my proof correct?
computer-science automata language-theory computer-science-theory
add a comment |
up vote
1
down vote
favorite
up vote
1
down vote
favorite
Q:
Show that L=ww is not context free
My solution:
Assume L is context free
Let its pumping length be P
thus,
string = 0^P 1^P 0^P 1^P
let P=2,
S= 00 11 00 11
S can be divided as u v^i x y^i z
0 0 110 0 11
u v x y z
after pumping,
0 00 110 00 11
u v x y z
0^3 1^2 0^3 1^2
therefore its takes the form of ww ( first condition met)
|vy|=4>0
(second condition met)
|vxy|= 7 which is greater than pumping length 2
(3rd condition is not met)
Therefore, contradicts assumption that L is context free.
Thus L is not context free
Is my proof correct?
computer-science automata language-theory computer-science-theory
Q:
Show that L=ww is not context free
My solution:
Assume L is context free
Let its pumping length be P
thus,
string = 0^P 1^P 0^P 1^P
let P=2,
S= 00 11 00 11
S can be divided as u v^i x y^i z
0 0 110 0 11
u v x y z
after pumping,
0 00 110 00 11
u v x y z
0^3 1^2 0^3 1^2
therefore its takes the form of ww ( first condition met)
|vy|=4>0
(second condition met)
|vxy|= 7 which is greater than pumping length 2
(3rd condition is not met)
Therefore, contradicts assumption that L is context free.
Thus L is not context free
Is my proof correct?
computer-science automata language-theory computer-science-theory
computer-science automata language-theory computer-science-theory
edited Nov 11 at 4:08
asked Nov 10 at 15:10
learner
133
133
add a comment |
add a comment |
1 Answer
1
active
oldest
votes
up vote
0
down vote
This proof is not correct. Where it goes off the rails is here:
let P=2, S= 00 11 00 11
You cannot "let" P be anything. P is assumed to exist due to the pumping lemma for context-free languages, but it is an as-of-yet hypothetical number. Even if the rest of the proof is correct, all you will be proving is that the number P=2 does not work. You need to prove that there is no choice for P in order to show the language isn't context-free.
The next mistake is this:
S can be divided as u v^i x y^i z […]
It's true that S can be divided as you propose. However, it can be divided other ways, too. Note that the pumping lemma for context-free languages only requires that |vxy| < P and |vy| > 0. In particular, any of u, v, x, y and z can be the empty string, so long as both v and y are not empty.
You were definitely on the right track with this:
string = 0^P 1^P 0^P 1^P
From here, rather than choosing a specific P or a specific assignment, consider interesting kinds of assignments, or cases, as a whole; the number of distinct cases that are interesting is actually quite small.
- v and y consist only of 0s from the first section of the string. Pumping causes the number of 0s in the first part not to match the next three parts.
- v and y consist only of 0s and 1s from the first and second sections of the string. Pumping causes the number of 0s and/or 1s from the first and second sections of the strings not to match the third and fourth sections.
- v and y consist only of 1s from the second section of the string. Basically the same as (1)
- v and y consist of 1s and 0s from the second and third sections of the string. Basically the same as (2)
- v and y consist of 0s from the third section of the string. Basically the same as (1) and (3)
- v and y consist of 0s and 1s from the third and fourth sections of the string. Basically the same as (2) and (4)
- v and y consist of 1s from the fourth section of the string. Basically the same as (1), (3) and (5).
These cases cover all possible assignments of v and y, and none of them can be pumped like the lemma says. This is the contradiction. The key is using |vxy| < P to limit the number of interesting cases (because |vxy| < P, v and y can consist of symbols only from adjacent sections). We never said what number P was; in fact, there is only a value for P if the language is context-free (then, P is closely related to the number of states in a pushdown automaton which accepts the context-free language).
add a comment |
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
0
down vote
This proof is not correct. Where it goes off the rails is here:
let P=2, S= 00 11 00 11
You cannot "let" P be anything. P is assumed to exist due to the pumping lemma for context-free languages, but it is an as-of-yet hypothetical number. Even if the rest of the proof is correct, all you will be proving is that the number P=2 does not work. You need to prove that there is no choice for P in order to show the language isn't context-free.
The next mistake is this:
S can be divided as u v^i x y^i z […]
It's true that S can be divided as you propose. However, it can be divided other ways, too. Note that the pumping lemma for context-free languages only requires that |vxy| < P and |vy| > 0. In particular, any of u, v, x, y and z can be the empty string, so long as both v and y are not empty.
You were definitely on the right track with this:
string = 0^P 1^P 0^P 1^P
From here, rather than choosing a specific P or a specific assignment, consider interesting kinds of assignments, or cases, as a whole; the number of distinct cases that are interesting is actually quite small.
- v and y consist only of 0s from the first section of the string. Pumping causes the number of 0s in the first part not to match the next three parts.
- v and y consist only of 0s and 1s from the first and second sections of the string. Pumping causes the number of 0s and/or 1s from the first and second sections of the strings not to match the third and fourth sections.
- v and y consist only of 1s from the second section of the string. Basically the same as (1)
- v and y consist of 1s and 0s from the second and third sections of the string. Basically the same as (2)
- v and y consist of 0s from the third section of the string. Basically the same as (1) and (3)
- v and y consist of 0s and 1s from the third and fourth sections of the string. Basically the same as (2) and (4)
- v and y consist of 1s from the fourth section of the string. Basically the same as (1), (3) and (5).
These cases cover all possible assignments of v and y, and none of them can be pumped like the lemma says. This is the contradiction. The key is using |vxy| < P to limit the number of interesting cases (because |vxy| < P, v and y can consist of symbols only from adjacent sections). We never said what number P was; in fact, there is only a value for P if the language is context-free (then, P is closely related to the number of states in a pushdown automaton which accepts the context-free language).
add a comment |
up vote
0
down vote
This proof is not correct. Where it goes off the rails is here:
let P=2, S= 00 11 00 11
You cannot "let" P be anything. P is assumed to exist due to the pumping lemma for context-free languages, but it is an as-of-yet hypothetical number. Even if the rest of the proof is correct, all you will be proving is that the number P=2 does not work. You need to prove that there is no choice for P in order to show the language isn't context-free.
The next mistake is this:
S can be divided as u v^i x y^i z […]
It's true that S can be divided as you propose. However, it can be divided other ways, too. Note that the pumping lemma for context-free languages only requires that |vxy| < P and |vy| > 0. In particular, any of u, v, x, y and z can be the empty string, so long as both v and y are not empty.
You were definitely on the right track with this:
string = 0^P 1^P 0^P 1^P
From here, rather than choosing a specific P or a specific assignment, consider interesting kinds of assignments, or cases, as a whole; the number of distinct cases that are interesting is actually quite small.
- v and y consist only of 0s from the first section of the string. Pumping causes the number of 0s in the first part not to match the next three parts.
- v and y consist only of 0s and 1s from the first and second sections of the string. Pumping causes the number of 0s and/or 1s from the first and second sections of the strings not to match the third and fourth sections.
- v and y consist only of 1s from the second section of the string. Basically the same as (1)
- v and y consist of 1s and 0s from the second and third sections of the string. Basically the same as (2)
- v and y consist of 0s from the third section of the string. Basically the same as (1) and (3)
- v and y consist of 0s and 1s from the third and fourth sections of the string. Basically the same as (2) and (4)
- v and y consist of 1s from the fourth section of the string. Basically the same as (1), (3) and (5).
These cases cover all possible assignments of v and y, and none of them can be pumped like the lemma says. This is the contradiction. The key is using |vxy| < P to limit the number of interesting cases (because |vxy| < P, v and y can consist of symbols only from adjacent sections). We never said what number P was; in fact, there is only a value for P if the language is context-free (then, P is closely related to the number of states in a pushdown automaton which accepts the context-free language).
add a comment |
up vote
0
down vote
up vote
0
down vote
This proof is not correct. Where it goes off the rails is here:
let P=2, S= 00 11 00 11
You cannot "let" P be anything. P is assumed to exist due to the pumping lemma for context-free languages, but it is an as-of-yet hypothetical number. Even if the rest of the proof is correct, all you will be proving is that the number P=2 does not work. You need to prove that there is no choice for P in order to show the language isn't context-free.
The next mistake is this:
S can be divided as u v^i x y^i z […]
It's true that S can be divided as you propose. However, it can be divided other ways, too. Note that the pumping lemma for context-free languages only requires that |vxy| < P and |vy| > 0. In particular, any of u, v, x, y and z can be the empty string, so long as both v and y are not empty.
You were definitely on the right track with this:
string = 0^P 1^P 0^P 1^P
From here, rather than choosing a specific P or a specific assignment, consider interesting kinds of assignments, or cases, as a whole; the number of distinct cases that are interesting is actually quite small.
- v and y consist only of 0s from the first section of the string. Pumping causes the number of 0s in the first part not to match the next three parts.
- v and y consist only of 0s and 1s from the first and second sections of the string. Pumping causes the number of 0s and/or 1s from the first and second sections of the strings not to match the third and fourth sections.
- v and y consist only of 1s from the second section of the string. Basically the same as (1)
- v and y consist of 1s and 0s from the second and third sections of the string. Basically the same as (2)
- v and y consist of 0s from the third section of the string. Basically the same as (1) and (3)
- v and y consist of 0s and 1s from the third and fourth sections of the string. Basically the same as (2) and (4)
- v and y consist of 1s from the fourth section of the string. Basically the same as (1), (3) and (5).
These cases cover all possible assignments of v and y, and none of them can be pumped like the lemma says. This is the contradiction. The key is using |vxy| < P to limit the number of interesting cases (because |vxy| < P, v and y can consist of symbols only from adjacent sections). We never said what number P was; in fact, there is only a value for P if the language is context-free (then, P is closely related to the number of states in a pushdown automaton which accepts the context-free language).
This proof is not correct. Where it goes off the rails is here:
let P=2, S= 00 11 00 11
You cannot "let" P be anything. P is assumed to exist due to the pumping lemma for context-free languages, but it is an as-of-yet hypothetical number. Even if the rest of the proof is correct, all you will be proving is that the number P=2 does not work. You need to prove that there is no choice for P in order to show the language isn't context-free.
The next mistake is this:
S can be divided as u v^i x y^i z […]
It's true that S can be divided as you propose. However, it can be divided other ways, too. Note that the pumping lemma for context-free languages only requires that |vxy| < P and |vy| > 0. In particular, any of u, v, x, y and z can be the empty string, so long as both v and y are not empty.
You were definitely on the right track with this:
string = 0^P 1^P 0^P 1^P
From here, rather than choosing a specific P or a specific assignment, consider interesting kinds of assignments, or cases, as a whole; the number of distinct cases that are interesting is actually quite small.
- v and y consist only of 0s from the first section of the string. Pumping causes the number of 0s in the first part not to match the next three parts.
- v and y consist only of 0s and 1s from the first and second sections of the string. Pumping causes the number of 0s and/or 1s from the first and second sections of the strings not to match the third and fourth sections.
- v and y consist only of 1s from the second section of the string. Basically the same as (1)
- v and y consist of 1s and 0s from the second and third sections of the string. Basically the same as (2)
- v and y consist of 0s from the third section of the string. Basically the same as (1) and (3)
- v and y consist of 0s and 1s from the third and fourth sections of the string. Basically the same as (2) and (4)
- v and y consist of 1s from the fourth section of the string. Basically the same as (1), (3) and (5).
These cases cover all possible assignments of v and y, and none of them can be pumped like the lemma says. This is the contradiction. The key is using |vxy| < P to limit the number of interesting cases (because |vxy| < P, v and y can consist of symbols only from adjacent sections). We never said what number P was; in fact, there is only a value for P if the language is context-free (then, P is closely related to the number of states in a pushdown automaton which accepts the context-free language).
answered Nov 12 at 14:23
Patrick87
17.6k32659
17.6k32659
add a comment |
add a comment |
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%2fstackoverflow.com%2fquestions%2f53240271%2fpumping-lemma-for-cfl%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