Limitations of regular languages pt. 2

Using the Pumping Lemma to Prove Non-Regularity (The Game)

To prove a language L is not regular using the Pumping Lemma, treat it as a game:

1. Demon picks a pumping length k > 0.

2. You pick a string s in L with |s| ≥ k. You must cleverly choose s based on the chosen k.

3. Demon splits s = xyz, where |y|>0 and |xy|≤k. They can pick any split.

4. You pick an integer i ≥ 0 (often i=0 or i=2) to pump y.
   You win (proving L is non-regular) if you can always pick s and i such that the pumped string xy^i z is NOT in L.

Strategy: Picking the String s

Your choice of s in step 2 is critical. The string must:

1. Be definitely in the language L.

2. Be longer than or equal to the demon's k (|s| ≥ k).

3. Be structured so that any split xyz (with |xy|≤k) forces the pumpable part y to be made of only one type of symbol (e.g., all as if s = a^k b^k). This restricts the demon's options.

Strategy: Analyzing the Split (y = uvw)

Once the demon splits y = uvw (where v is the part you can repeat), you analyze the possible content of v. Because of condition |xy| ≤ k, y (and thus v) lies within the first k symbols of your chosen s. If s is chosen well, v can only contain one repeated symbol.

Strategy: Picking i to Win

After the demon's split, you pick an i (like 0 or 2) to break the pattern of the original language. For example, if L = {a^n b^n} and v consists of l as, then pumping to i=2 gives more as than bs, creating a string not in L. This contradiction proves L is not regular.

Example Game: Proving {a^n b^n} is Non-Regular

1. Demon picks k.

2. You pick s = a^k b^k (clearly in L, |s|=2k ≥ k).

3. Demon splits s = xyz with |xy|≤k. This forces y to be all as (say y = a^l, l>0).

4. You pick i=2. The new string is a^{k+l} b^k. This has more as than bs, so it's not in L.
   Since the demon cannot win with any split, L is not regular.

Proving Non-Regularity via Closure Properties (Intersection)

If you suspect L is not regular, try intersecting it with a simple regular language. If the intersection results in a known non-regular language, then L must also be non-regular (because the intersection of two regular languages is always regular). Example: To show P (palindromes) is non-regular, intersect with the regular language a*ba*. The result {a^n b a^n} is non-regular, so P must be too.

Proving Non-Regularity via Closure Properties (Complement)

If the complement of a language L (denoted ~L) is non-regular, then L itself must also be non-regular. This is because the class of regular languages is closed under complement: if L were regular, ~L would be too. Example: L' = {w ∈ {a,b}* | w ≠ a^n b^n} is non-regular because its complement {a^n b^n} is non-regular.

Example: Using Intersection on {a^n c^m b^n}

To prove L = {a^n c^m b^n | n, m ≥ 0} is non-regular:

1. Take a simple regular language, R = a* b*.

2. Compute the intersection: L ∩ R = {a^n b^n | n ≥ 0}.

3. We know {a^n b^n} is not regular.

4. If L were regular, then L ∩ R would have to be regular (closure under intersection).

5. Since it's not, L cannot be regular.

The Demon Game: Why it Works (Logic)

The game formalizes the contrapositive of the Pumping Lemma. The lemma says: "If regular → can be pumped." The contrapositive is: "If cannot be pumped → not regular." In the game, "cannot be pumped" means you have a winning strategy: for every k, you can find an s such that for every allowed split, you can find an i that breaks the language.

Key Takeaway: Combining Techniques

The most powerful approach is to combine the Pumping Lemma with closure properties. Often, directly applying the Pumping Lemma to a complex language is hard. First, use operations like intersection with a regular language or homomorphism to transform it into a simpler, known non-regular language (like {a^n b^n}), then apply the Pumping Lemma or a known result to that simpler language.