Pumping lemma

[YugoTrek]

Hi.

There are two Pumping Lemmas.

One for regular languages, For example a^n.

L = {a^n b^n c^n} Regular means that all letters have n, which is same, right?

If we have a word, let's say, aabbcc, then
how this pumping works? You pump in one part?

I have seen that some people use uvwxy, and that's
fine for me.

I try. aabbcc. Let's choose that aa = v
aaabbcc

and next step would be:
aaaabbcc

And you can pump with value 0? Why with 0?



Other lemma is for context-free languages, For example a^n b^m c^k.

L = {a^n b^m c^k} Now, all letters have different exponent

Let's choose that n=2, m=3, k=5.
If we have a word aabbbccccc

How this pumping works?, You pump NOW in two parts?
And you can pump with value 0?

I try. Let's choose that bbb=v and ccccc=w
aabbbbcccccc

Netx step would be:
aabbbbbccccccc

But I don't know have I understood these lemmas, how they work?

[phlip]

But I don't know have I understood these lemmas, how they work?

Not... really.

The pumping lemmas are a statement that, if you have a language in a particular class (regular, or context-free) then you can peform some operation on it. You seem to at least have a vague understanding of what that operation is... but you don't seem to understand what the point is?

Well, what it means is that if you can show that particular operation can't be done for a certain language, then you can use the lemma to say that the language isn't regular, or context-free. For example, if you can't pick a number p such that every string in the language longer than p can be broken up and repeated in the appropriate way and stay in the language, then you've proven that the language can't be regular/context-free (depending on which pumping rule you used).

[Yakk]

We can back up a second.

The pumping lemma is one of the few ways to demonstrate that a language isn't regular (or context free).

Before we touch on the CFG language case, let's work on the simpler one. The pumping lemma for regular languages.

Have you any exposure to automata theory? The idea that all regular languages are the strings that a "finite automata" with no external state (a pure finite automata) can categorize as being in/out of a set (or, can "recognize")?

If a language is regular, we need to be able to build a relatively simple machine (a finite automata) that can "understand" it. While any given machine isn't likely to recognize our language, what makes a language regular is that there is at least one such machine. Proving that there are no machines that recognize your language is tricky without checking each one -- and as there are an infinite number of finite automata, this could take a while.

So instead what we do is find some property that all finite automata share. In this case, it is the fact that, given a long enough input, they will have no choice but to go into a loop.

Each finite automata has only a finite number of states, so it cannot "remember" an unbounded amount of stuff. If it has 2 billion states, and you feed it a string more than 2 billion characters long, it will either (A) reject the string, or (B) at some point return to a state it was in previously.

And the behavior of a finite automata is completely and utterly determined by which state it is in. So if it gets back to a previous state, you are guaranteed that if you look at the string between the two times it was in the two states, you can repeat that string over and over and over and over again, and your finite automata will keep on being happy and returning to its repeat state.

The pumping lemma is a formalization of this. It says that every finite automata has a maximium size. And if you exceed this maximum size in an input that it doesn't reject, it will repeat a state. And that the part of the input between the instances of the repeat state can be repeated any number of times, and that the automata will keep on accepting it.

Now, we are trying to prove that a language isn't regular. So first we say "assume it is regular". If it is regular, it has a finite automata that recognizes it. This finite automata has some finite size. We craft a string larger than the size of the automata (even though we don't know exactly how big it is, so our crafting procedure has to handle any size of finite automata), and note that the automata will have to accept it even if we repeat some substring in the middle. If we can find such a substring in an arbitrarily long input whose repetition doesn't keep the string in the language, then we know that our assumption was false.

Does that make sense?

Part of the problem is that this might be your first real contact with formal logic, and proof by contradiction. Having to hold a claim in your head as "pretending it is true" that you later prove to be false is tricky for some people.

[YugoTrek]

Hi. Thanks. Well, I knew that The pumping lemma is a way to demonstrate that a language is not regular or context free. Sorry that I didn't say that.

But I don't know how that pumping goes...

[Yakk]

So, all you got from my long post was "the pumping lemma is used to show that a language is not regular".

Really? That is all you got from that entire post? Followed by "But I don't know how that pumping goes..."?

If you want to know what you are doing with these lemmas, you can either do a monkey-see, monkey-do approach, where you find someone else's use of the lemma and blindly try to duplicate the patterns. Or you could understand what it is that the pumping lemma represents, and actually understand why it works, after which understanding what kind of attacks on "possible regular languages" that the pumping lemma allows makes sense.

And, once again, you shouldn't even be touching the pumping lemma on regular languages until you understand completely the pumping lemma on regular languages. Learn the simpler cases first, then the more complex ones.

Regular means that all letters have n, which is same, right?

That you are saying things like this, means you do not understand what a regular language is.

You obviously have some serious problems understanding the theory of computer science that is much deeper than "the pumping lemma -- what does it pump". You do need to back up and fix your complete lack of understanding of what "regular languages" are before you start trying to use the pumping lemma to prove things aren't regular.

I will admit that won't help you pass your next test, but the test after your next test is a write off unless you start getting a clue.

As for your other questions:

how this pumping works? You pump in one part?

And you can pump with value 0? Why with 0?

Both of these questions are really easy to answer if you go and actually read my last post, and understand what it says. If you don't understand my last post, then about all I could do is give you a monkey-see, monkey-do level of understanding, where you blindly duplicate what someone else does, hoping that the magical grades arrive after you complete the incantation.

So go back and read that post I spent time composing, and work out where you are having problems. If you understand it, the answers to the above questions fall right out. If, instead, you glance at it, skip it, and whine, well, that isn't my problem is it?

[alouette]

@Yakk, thanks for your post. I was hoping if you would elaborate or continue the conversation because I am in the same boat as the OP, but after reading your post, I understood the motivation of the pumping lemma for the first time because of the way you structured your explanation.

I'd love to clarify a step right before we use the pigeonhole principle to help to formalize why at least one state had to have been repeated: to read a string of length n, a finite automata will always need the string to have passed through n+1 states? Or if that's not correct to say, I mean that the string will be in n+1 state?

And why is it that only one non-empty string is pumped? Or rather, why is a string w in L only broken down into 3 strings? Why not 5 as in the context-free languages, where two strings are pumped. Sidenote: I'm not any further in understanding the Pumping Lemma in the CFL case, but I'm guessing the two pumped strings has to with the fact that a language in Chomsky Normal Form can be parsed either A --> <some non-terminal variable> or A --> <some terminal symbol> ? ) Maybe my question should be, what am I not understanding that makes me question why only one string would be pumped? Maybe I'm unknowingly missing some key difference between CFL's and regular languages. But I ask the question because the language L = {w | w has equal number of 01 and 10 substrings} is regular. So my fuzzy logic makes me think that two strings are getting pumped but of course I can't use the pumping lemma to prove that this language is regular.

[Yakk]

Maybe there will be more than one loop -- but you cannot guarantee that there will be more than one loop. I'd advise reading over the proof of the pumping lemma (for regular languages).

I'll sketch the proof in pseudo-english. This is written in the context of this previous post of mine, for those joining us at home.

Suppose a language L is regular, recognized by some FSM M. Then for some N, M has N states (we don't know what N is!).

Now, suppose L contains a string S such that |S| > N.

Claim 1: when recognizing S, M uses (at least one) state twice. Let a state that is used twice when recognizing S be called Bob.

If M uses the same state twice, we break the string S into three parts. a b and c. a is the part of S that occurs before we reach Bob for the first time while recognizing S. b is the part of the string that starts when we first reach Bob while recognizing S, and ends at the next time we reach Bob. c is the rest of S after the 2nd time we reach Bob.

So S = a b c

Claim 2: a b^n c is in L, for all n >= 0.

And that is the pumping lemma for regular languages.

---

The two claims can be proven pretty easily.

The first Claim is proven by the pigeonhole principle. When recognizing a string, M transitions from one state to another. If it stays in the same state as it reads a character, that is a really short loop. So to recognize a string of length S without visiting a state twice, it needs |S| states, but it only has N states, and N < |S| by a previous assumption. So it must visit a state twice!

The second Claim would be formally proven by induction, but the main idea is pretty simple. After reading a, we are in state Bob. And, if we are in state Bob and get the string c, we end up accepting. So a c is accepted. So is a b c. Now, b starts in state Bob and ends in state Bob -- but the same is true of b b and b b b and b b b b and b b b b b. So a b b b b b b b c is also accepted: in fact, a X c, where X is any string such that if the machine M started in state Bob, would be back in state Bob after reading X, is accepted. We happen to know that b^n has this property -- so we know that a b^n c has this property.

The real trick here is that the only assumptions we made was that L is a regular language. We then talked about properties it must have (even if we cannot explicitly find them) for it to be regular. And from that, we constructed the conclusion of the pumping lemma.

There could in fact be multiple loops in how M recognizes (at least one string) in L -- but we cannot prove this. And, there is no reason for two loops to be "in sync" like with the CFG one -- in fact, if the language requires that they be in sync, then you cannot recognize it with a FSM!

(The CFG one has two loops in sync because of the limited memory that CFGs recognizers have). You can view this as a property of CNF grammars, or you can make an argument about pushdown automata. The CFG pumping lemma is a bit nastier to prove -- but the main idea (that a you can find a structure in a string in which the CFG parser can be forced to "loop" over) is the same, but because of the increased complexity of said parser the structure is more complex.