Pumping lemma on regular languages?

Question

I am a bit confused on the theory of the pumping lemma. As I know is used to decide if a language is regular or not. There is a variable let be m such that is the states?

x = vxu
Where vx >= m
And u not ε (>=1)
and a variable i such that v(x^i)u

So i cant understand how this is working. I mean where is that useful? By breaking a string into 3 parts and repeat the x? And how is that showing if it is regular or not? And is any difference between pumping lemma for regular languages and context-free languages?

Answer 1

The pumping lemma is this:

For a regular language L, there exists a p > 0 such that for all w ∈ L where |w| ≥ p, there exists some split w = vxu, for which the following holds:

• |vx| ≤ p
• |x| > 0
• vxⁱu ∈ L for all i ≥ 0

The reason I stated it again is because some of your inequalities are wrong.

What is the pumping lemma useful for?

The only use of the pumping lemma is in determining whether a language is specifically not regular. I.e. if a language does not follow the pumping lemma, it cannot be regular. But just because a language pumps, does not mean it is regular (This lemma is used in Contrapositive proofs).

How does it show whether it is regular?

As I said above, it doesn't, there are some pumpable languages which are not regular (EDIT Wikipedia has an example of a language that satisfies the pumping lemma but is not regular here), however, I think maybe the question you want to ask is this: Why is it that all regular languages can be pumped?

Why is it that all regular languages can be pumped?

Consider the characterisation of a regular language, as being recognised by some Discrete Finite Automaton, M, with some finite number of states n.

Then, consider some string in the language of M, which we shall call w, for which |w| ≥ n holds true.

In checking w, M must pass through |w| + 1 states (including its start and end states). So, by the pigeonhole principle, M must pass through some states more than once (because |w| + 1 > n).

Let w = a₁a₂...a_n

Imagine these are the state transitions of M, starting at q_s and ending at q_f, in processing w:

  a1   a2   a3 ... an
qs → q1 → q2 → ... → qn = qf

Now let's look at the section of these state transitions where M repeats a state, we'll call that state R:

  a1   a2   a3     ar      ar+1   ar+2   ar+k       ar+k+1   ar+k+2  an
qs → q1 → q2 → ... → qr = R → qr+1 → ... → qr+k = R → qr+k+1 → ... → qn = qf

Let us use a shorthand here to say this:

  a1   a2   a3     ar
qs → q1 → q2 → ... → qr

is the same as this:

   v
qs →* qr

where v = a₁a₂...a_r

Now let us split w into three parts, w = vxu, in the following way:

v = a1a2...ar
x = ar+1ar+2...ar+k 
u = ar+k+1ar+k+2...an 

Now we see that for v:

   v
qs →* R

And for x:

  x
R →* R

And for u:

  u
R →* qf

(All I have done is split up the longer state transition diagram above into three separate ones)

Here you see that M will also accept vu, vxxu, vxxxu, ..., vxⁱu for i ≥ 0, because processing the string x at state R, keeps M in state R.

Essentially, the purpose of the pumping lemma is to find that bit of the string that does not alter the state of M when processed.

Now you may wonder. What if there are no strings recognised by M for which |w| ≥ n holds true?

Well, in that case, you can infer that the language is regular, simply by the fact that it is finite (All finite subsets of ∑* are regular), and furthermore, the pumping lemma is vacuously true, you simply choose a pumping length p > n, and you can be sure that all strings recognised by M that also satisfy |w| ≥ p can be pumped (because you know that none exist).

Is the pumping lemma for context free languages different?

Yes, here it is:

For a context-free language L, there exists a p > 0 such that for all w ∈ L where |w| ≥ p, there exists some split w = uxyzv for which the following holds:

• |xyz| ≤ p
• |xz| > 0
• uxⁱyzⁱv ∈ L for all i ≥ 0

The proof for it is a bit more involved, and this answer is already pretty long, so here's the sketch:

Essentially, what this lemma is taking advantage of is another pigeonhole principle style argument, but this time, focusing on the number of variables in the context-free grammar, and the length of its largest production.

Using this information, it's possible to see that for a given grammar, there are some strings large enough that they require a part of the parse tree to be replicated, within itself. This part of the parse tree is xyz, and what is happening, is the y is being replaced by another xyz.

This lemma also can be vacuously true if the language is finite, and is also used in the Contrapositive, like the pumping lemma for regular languages.

If you need more information, I recommend Introduction to the Theory of Computation by Michael Sipser. It has some good sections on both pumping lemmas, and I feel it explains them very well.