A detail on the Pumping Lemma for regular languages

Question

I have one small question about the pumping lemma for regular languages - is it good enough to show that if a specific string belonging to a language L can't be pumped, then the language is irregular? For example - if I choose language L1 being of the form a^nb^n (ab, aabb, aaabbb ...) and I show that the string aabb can't be pumped and still be a part of L1, then is it valid for me to immediately conclude that L1 is irregular?

Cheers.

Answer 1

Yes, that's how the pumping lemma works. It's only useful for proving languages to not be regular. Satisfying the pumping lemma is only a necessary but not a sufficient condition for a language being regular.

(Nota bene: Likewise for context-free languages and the respective pumping lemma there)

Answer 2

Yes, this is how it works, but be careful in showing how a string "cannot be pumped"

To do that you have to break a string w in L, into substrings xyz and show that some versions of xy^1z, for int i i>=0 lead to strings not in L, but are still accepted by DFA M (for M built to accept L), arriving at a contradiction.

Note that you cannot pick the location of y and therefore must consider 3 possible positions of it. That's the key, in my opinion.

Answer 3

It's not quite sufficient to demonstrate that a single, finite-length string does not pump. For a rigorous argument, you'd also have to prove that length of your example string is greater than the pumping length of the language. Usually you assume that some pumping length p exists, then construct a string longer than p that cannot be pumped.

Answer 4

The pumping lemma says: If a language A is regular => there is a number p (pumping length) where, if s is any string in L such that |s| >= p, then s may be divided into three pieces s=xyz, satisfying the following condition:

1. xyⁱz is in L for each i>=0
2. |y|>=0
3. p>=|xy|

The right way to show that a certain language L is not regular is to suppose L regular and try to reach a contradiction.

Lets try to demonstrate that L = {0ⁿ1ⁿ}|n>=0} is not regular. We start assuming to the contrary that L is regular.

You can think about this kind of demonstration as a game:
Challenger: He choose the pumping length p. You cannot do any presumption on it.
You: Now it is your turn: choose the "kind" of string that represents the irregularity of the language.
Lets say that the string is in the form 0^p1^p.
A good tip in this step is to try to limit the adversary next move.
Challenger: He presents to you a string s in the form 0^p1^p.
You: It's time to pump! If you chose correctly the form of the string in your previous move, you can do some assumption.
In our case, for example, we know that the substring y consists only of 0s (at least one 0 because |y|>0), because |xy|<=p and first p-elements are 0s.

Now we show that it exists i>=0 such that xyⁱz is not in L. For example, for i=2 the string xyyz has more 0s than 1s and so is not a member of L. This case is a contradiction. => L is not regular.

Never forget to demonstrate why the pumped string cannot be a member of L.

Probably it is late to help you, but someone else may need this kind of explanation...maybe ^^

Cheers.