proof by pumping lemma

[wholegrain]

we have L {a^m b^n: n = 4m}

 

we choose a string w = a^m b^4m

 

if we pump 1 a we'd get a^(m+1)b^4m, which doesn't meet n = 4m

 

that's it?

 

is this a valid proof?

[John]

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 February 19, 2014 by John

[wholegrain]

Yeah, well I wrote something like Assume w is in the regular language, wrote the conditions for uvw and then just pumped once. It seems a bit too easy in some case, am I doing something wrong?

[John]

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 February 19, 2014 by John

[wholegrain]

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.

[John]

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 uv²z) 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. But no matter.

Edited February 19, 2014 by John

[wholegrain]

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 i≠1 to select a word uviw. If uviw is not in L, you win. But if uviw is in L, you lose.

Edited February 19, 2014 by wholegrain

[John]

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, xyⁱz 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 February 19, 2014 by John

[wholegrain]

so can you pick a particular u v and x or do you only have the luxury to choose a particular w?

[John]

You can choose any w in L, as long as you show |w| ≥ p. Then you can decompose w into uvx any way you like as long as |uv| ≤ p and |v| ≥ 1.

Edited February 19, 2014 by John

[wholegrain]

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...

[John]

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 = {a^mbⁿ: 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 February 19, 2014 by John

[wholegrain]

actually i was referring to another problem where we have the condition m not equal to n, and i have no idea what to do. actually, i think i am in a dead end and i have to choose another string.

[John]

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 m ≠ n), consider the string w = a^pb^p+1 (spoiler alert: this one won't work--it's just an example of the reasoning). Decompose it into the substrings u = a^p-1, v = a, and z = b^p+1. Then for i = 2, we have uv²z = a^p-1a²b^p+1 = a^p+1b^p+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 = a^p-2, v = a², and z = b^p+1. Now, for i = 1, we have our original string uvz = a^p-2a²b^p+1 = w. For i = 2, we have uv²z = a^p-2a⁴b^p+1 = a^p+2b^p+1, which is in the language. For i = 3, we have uv³z = a^p-2a⁶b^p+1 = a^p+4b^p+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 February 19, 2014 by John