Nonregular Languages

All regular languages have a property that proves that they are regular.

This property is that all strings in the language can be “pumped” if they are at least as long as a certain special value, called the pumping length.
- This means each such string contains a section that can be repeated any number of times with the resulting string remaining in the language.

Example:
C = \{ w | w \text{ has an equal number of 0s and 1s} \} \\~\\
D = \{ w | w \text{ has an equal number of occurrences of 01 and 10 as substrings } \}
Observations:
C is not regular
D is regular

Layperson’s:
If a language is regular, it can recognize an infinite set of strings.
If machine can’t loop, it’ll run out of states.
Thus, to accept infinite-length strings, you need a repeating portion (the pumped portion).

Pumping Lemma

If A is a regular language, then there is a number p (the pumping length) where if |s| \ge p, then s may be divided into three pieces, s=xyz, satisfying the following conditions:

for each i \ge 0, xy^iz \in A,
|y| > 0, and
|xy| \le p

Observations:

x or z may be $, but y \ne \epsilon (condition 2)
- aka: cycle (y) cannot by empty (length zero)
x and y together must have a length at most p (condition 3)
All strings longer than the pumping length be pumped (|s| \ge p)

Remember: Pumping Lemma is used to prove a language is NOT regular.
It cannot be used to prove that a language is regular.
We do proof by contradiction because it’s much harder to prove nonexistence; that we cannot make an NFA that recognizes a language.
e.g., “All classrooms contain a Unicorn” can be proven wrong by just finding one classroom without a Unicorn

Usage

How-to Use Pumping Lemma:

Assume A is regular
It has to have a Pumping Length (P)
All strings longer than P can be pumped |S| \ge P
Now find a string S in A such that |S| \ge P
Divide S into xyz
Show that xy^iz \not\in A for some i
Then consider all the ways that S can be divided into xyz.
Show that none of these can satisfy all the 3 pumping conditions at the same time.
If S cannot be pumped, then A is not regular.

Remember: Don’t give p a concrete value!

Related Notes: Proof by Contradiction (CS1300)

Example: Pumping Lemma

Q: Is L = \{ a^n b^n | n \ge 0 \} regular?

Assume L is regular so pumping lemma applies on L

Let p be the pumping length, then any string in L where |s| \ge p, there exists strings x, y, z such that s = xyz and:

xy^iz \in L for each i \ge 0, and
|y| \ge 0, and
|xy| \ge p

Consider the string a^p b^p, s \in L and |s| \ge p

Looking at condition 3, we can smartly see that the maximum we can cut is up to middle of our string, as |a^p| = p, so cutting any further would violate condition 3.

Thus, xy can only contain zero or more a’s

But/further, from condition 2, y can only contain one or more a’s.

Let’s consider condition 1 when i=0.

xy^iz = xz \in L
xy has one or more a’s (definition of y) removed from s, resulting in fewer a’s than b’s
This violates L = \{a^n b^n\}, so xz \not\in L, which is a contradiction.

\therefore L must not be regular language.

Note: If a language is finite (e.g., \{ a^n b^n | n \le 7 \}), it is a regular language because a DFA can clearly be made.