Jump to content

proof by pumping lemma


wholegrain

Recommended Posts

Well, the general argument seems reasonable, but a formal proof using the pumping lemma will require some fleshing out. You'll want to assume your language is regular (or context-free, etc., depending on which property you're trying to prove), then use the properties guaranteed by the appropriate pumping lemma to arrive at a contradiction, i.e. to show that the result of applying the pumping lemma to your language is a string not in the language.

Edited by John
Link to comment
Share on other sites

It's not really a matter of doing something wrong. It's more that some steps have been left out.

For instance, you mention pumping once, but the pumping lemma simply asserts that there exists some integer p ≥ 1 such that every string w in L with length at least p satisfies the various properties. So it's better to start by assuming that there does exist such a p, then continue on to show that, given the other properties guaranteed by the lemma, the result is a string not in L.

Wikipedia actually offers a decent example which is common enough that you may have seen it before.

Edit: Rereading your posts, it may be that you have a fully fleshed out proof written and simply haven't shared it all with us. If you'd like to post the entirety of what you have, it'd be appreciated.

Edited by John
Link to comment
Share on other sites

ummm....... yeah actually my question wasn't: is this a valid proof, because it sure isn't but whether i can just pump once for that one by choosing a string that will make it immediately wrong once i pump it once, and also whether i can choose any v, or it has to work with any v.

Link to comment
Share on other sites

Well, once you've decomposed your string w into uvz (I changed uvw to uvz because the entire string is w), the restrictions are that |uv| ≤ p and |v| ≥ 1. As far as I can tell, for any valid string and any valid decomposition uvz, pumping once (which corresponds to setting i = 2 such that the resulting string is uv2z) is enough, but the idea is to show that it's enough for some string w in L, which you halfway did in your OP, but there are, as mentioned, gaps.

 

The last question in your original post asks whether the given statements constitute a valid proof. :P But no matter.

Edited by John
Link to comment
Share on other sites

my proof goes like this

 

w = a^m b^4m

 

|uv| = n |v| > 0 uvx = w

 

a^(k+i(m-k)b^4m

 

let k = 2

 

if i = 2 then 2m-2 != m

 

i am pretty sure this is wrong, can you tell me of a systematic way to solve these kind of problems, or a way that works 99% of the time? i have no intuition at all for these sort of things

 

 

also, do i have to prove for all u, v and x, or can i choose a particular, u, v and x?

 

 

someone told me this and it confused the hell out of me:

 

  1. Mr. Pumping Lemma gives you a pumping constant p.

  2. You pick a string s of length at least p.

  3. Mr. Pumping Lemma divides s into three parts uvw, subject to the restrictions that |uv|p, |v|1.

  4. You now "pump" the v part by picking an integer i1 to select a word uviw. If uviw is not in L, you win. But if uviw is in L, you lose.

Edited by wholegrain
Link to comment
Share on other sites

I don't really know how to explain better than the way the Wikipedia article I linked earlier explains.

The general process is as follows. Given a language L:

1. Assume L is regular.

2. Choose a string w in L of length greater than p, where p is the pumping length guaranteed by the pumping lemma for regular languages.

3. Decompose w into three substrings xyz such that |xy| ≤ p and |y| ≥ 1.

4. Show that for some positive integer i, xyiz is not in L.

In your argument above, you haven't guaranteed the reader that w is of length greater than p, since m is an arbitrary value (which could be zero, making w the empty string ɛ). You also say that |uv| = n, but we aren't told what n is and it's never made clear from context in the rest of the argument.

 

Proof-writing doesn't come naturally for most people (myself included). Even in cases like this, where there's a general outline that seems to work, the details can be a pain, and learning to work through them proficiently is a matter of practice.

Bed-time for me, anyway. Best of luck on your assignment. :) Going back over your textbook, or whatever learning resources you're using, is probably a good idea. Sometimes you just have to stare at the material until it clicks. And of course, there are other pumping lemma proofs and examples around the Web if you care to Google.

Edited by John
Link to comment
Share on other sites

What happens if you have 2 conditions? Do you have to prove that both conditions doesn't hold after pumping once?

 

say we have condition A and B and we have something like L { something such that condition A holds or condition B holds} do we have to prove that both of them doesn't hold for a particular w?

 

Also, how do we prove that n = m? When you pump, you get n+x how can you prove that n+x = m? there are infinite number of cases...

Link to comment
Share on other sites

If the language consists of strings meeting two conditions, then showing that one condition fails is enough. If the language consists of strings meeting *at least one of* two conditions, then you must show that both conditions fail.

 

For your last question, I'm assuming you're referring to your original problem, in which L = {ambn: n = 4m}. Here you simply need to show that, in the resulting string, the required relation n = 4m doesn't hold, i.e. there are no longer four times as many b's as a's.

Edited by John
Link to comment
Share on other sites

Keep in mind that w can be *any* string in L with length at least p. Then it's a matter of checking the various valid ways in which w can be decomposed into uvz to see whether iterating v fails to give a new string in the language.

For instance, in this new problem (where mn), consider the string w = apbp+1 (spoiler alert: this one won't work--it's just an example of the reasoning). Decompose it into the substrings u = ap-1, v = a, and z = bp+1. Then for i = 2, we have uv2z = ap-1a2bp+1 = ap+1bp+1, which isn't in the language. This is all well and good, but we have to consider *all* possible decompositions of w. So consider u = ap-2, v = a2, and z = bp+1. Now, for i = 1, we have our original string uvz = ap-2a2bp+1 = w. For i = 2, we have uv2z = ap-2a4bp+1 = ap+2bp+1, which is in the language. For i = 3, we have uv3z = ap-2a6bp+1 = ap+4bp+1, which is in the language. And so on. Thus we have found a decomposition of w for which we generate a new string in L for any choice of i.

 

The question is, can you find a valid string w such that, given any valid decomposition of w, we generate a new string not in L for some value of i ≥ 1?

A hint: The empty string ɛ is a substring of any string.

Edited by John
Link to comment
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now
×
×
  • Create New...

Important Information

We have placed cookies on your device to help make this website better. You can adjust your cookie settings, otherwise we'll assume you're okay to continue.