5.1.1.1. The Concept of Pumping¶

Proof 2 (by contradiction, but worded a little differently)

Proof: Suppose that \(L_2\) is regular.

Then there exists DFA \(M\) that recognizes \(L_2\).

\(M\) has a finite number of states, say \(k\) states.

Consider a long string \(a^kb^k \in L_2\).

Since there are \(k\) states and \(k\) a’s (followed by some b’s), some state in \(M\) must be reached more than once when following the path of \(a^k\).

In that case, there is a loop with one or more a’s (say \(t\) a’s for some \(t > 1\)) along the path.

Suppose we start at the initial state, traverse the same path for \(a^kb^k\), but we traverse the loop of a’s one additional time (“pump” the loop). We will end up in the same final state that \(a^kb^k\) did.

Therefore, the string \(a^{k+t}b^k\) is accepted by \(M\), but this string is not in \(L_2\). Contradiction!

Thus, \(L_2\) is not regular.

In Proof 2, we introduce the concept of “pumping” the string as we go around the loop. Loops are how we get infinite languages. They are also how we lose count or otherwise lose the ability to distinguish various properties of the string being processed.

Another way of looking at it is that the memory of a DFA is embodied explicitly in its set of states. Since the number of states is finite, the memory is finite. Further, while a program in a traditional programming language might have one integer (that conceptually at least stores an infinite number of values, even if that is not literally true), a DFA has no such thing.

In general, consider a DFAs with or without cycles. If there is no cycle, the language accepted is finite. If there is one or more cycle, then the language is infinite. But we can actually say a bit more about this language. To explain the concept, let’s assume that there is exactly one cycle. In that case, the cycle might be skipped, executed once, or executed more than once.

We can consider any string accepted by this DFA when the cycle is executed exactly once to be of the form \(w = w_1vw_2\) where the \(v\) represents the part of the string captured by the cycle. Now, if the cycle is skipped, then we get \(w = w_1w_2\), and if its executed twice we get \(w = w_1v^2w_2\). In general, the DFA accepts all strings like \(w = w_1v^*w_2\).

5.1.1.2. Pumping Lemma¶

Settings

Saving...
Server Error
Resubmit

How To Use the Pumping Lemma to prove language L is not regular:

We will use a proof by Contradiction.

So we start by assuming that L is regular.

Therefore \(L\) satisfies the pumping lemma.

Choose a long string \(w \in L\), \(|w| \ge m\). The choice of the string is crucial. We must pick a string that will yield a contradiction.

Show that there is NO division of \(w\) into \(xyz\) (we must consider all possible divisions) such that \(|xy| \le m\), \(|y| \ge 1\) and \(xy^iz \in L \forall i \ge 0\).

If we show that there is NO possible division, then we have a contradiction!

\(\Rightarrow L\) is not regular.

Unfortunately, the pumping lemma is one-way: For (some) languages we can use the pumping lemma to prove that they are not regular. But we cannot use the pumping lemma to help us prove that a language is regular. And the pumping lemma is not a universal solution for determining that a language is non-regular. Its just a tool in the toolbox.

It is important to understand that the pumping lemma says that there is some way to define the language that meets the criteria. It is not enough to pick your favorite value of \(m\) for which the language would not be regular. You have to show that no satisfactory \(m\) can exist.

Here is an adversary argument way of looking at this. Your goal is to establish a contradiction (to prove the language is not regular), while the opponent tries to stop the proof. The moves in the game are:

1. The opponent picks \(m\).

2. We pick string \(w\) in \(L\) of length equal or greater than \(m\). We are free to chose any \(w\), so long as \(w \in L\) and \(|w| \geq m\).

3. The opponent chooses the decomposition \(xyz\), such that \(|xy| \leq m, |y| \geq 1\). The opponent will make the choice that is hardest for us to win the game.

4. We try to pick \(i\) so that the pumped string \(w_i = xy^iz\) is not in \(L\). If we can always do this, we win (\(L\) is not regular).

1. There exists a constant \(m > 0\) [= Adversary picks a value for \(m\).]

2. … such that any \(w \in L\) with \(|w| \ge m\) [= WE pick our choice for \(w\).]

3. … can be decomposed into three parts as \(w=xyz\) [= Adversary picks \(xyz\)] (that meets the length criteria on \(xy\) and \(y\))

4. … such that \(xy^iz \in L\) for all \(i\ge 0\) [= WE pick a value for \(i\).]

The following lets you play either side of the adversary argument “game”.

5.1.1.3. Use Closure Properties to prove \(L\) is not regular¶

Using closure properties of regular languages, construct a language that should be regular, but for which you have already shown is not regular. Contradiction.

Proof Outline:

Assume \(L\) is regular.

Apply closure properties to \(L\) and other regular languages, constructing \(L'\) that you know is not regular.

Closure properties \(\Rightarrow L'\) is regular.

Contradiction. So \(L\) is not regular.