Monday, December 1, 2008

Pumping lemma

The pumping lemma is a tool that we use to determine if a language is regular. In laymen's terms, the idea of the pumping lemma is that an accepted string past a certain length can be broken into parts and that no matter how many times these parts are repeated, the string will still be accepted by the language. More formally, If L is a regular language. Then there is some p that depends on L such that if x is an element of L and |x|>= p, then there exists substrings u,v,w such that x = uvw, where |uv| <= p, v is not empty , and for all k in the Natural numbers, w(uv^k) is an element of L. However, I am unclear on certain aspects of using the pushing theorem. The most trouble I seem to have is with how to break up the string x into uvw and whether we must consider all possible strings u,v,w that could collectively form x. Additionally I can see that a language that does not have the pumping lemma property is not regular, but I am unsure if a language that has the pumping language property is necessarily regular. After searching the internet a bit, it seems that the property apparently holds for some irregular languages, for example, (taken from the wikipedia page on pumping lemma for regular expressions): the language {u(u^R)v : u,v {0,1}+} (strings over the alphabet {0,1} consisting of a nonempty even palindrome followed by another nonempty string) is not regular but can still be "pumped" with p = 4. Suppose w=u(u^R)v has length at least 4. If u has length 1, then |v| ≥ 2 and we can take y to be the first character in v, thus not affecting the palindromic requirement. Otherwise, take y to be the first character of u and note that yk for k ≥ 2 starts with the nonempty palindrome yy, so it's still in the language. I would like to see a bit of attention paid to this example in class, because it seems to be an interesting example of where the pumping theorem may fail.

No comments: