🧠 Introduction to Pumping

🎯 What is the Pumping Lemma?

The Pumping Lemma is a tool for proving that a language is NOT regular (or NOT context-free). It says: every sufficiently long string in a regular language can be "pumped" — a middle section can be repeated any number of times and the result is still in the language.

Key insight: The lemma is a necessary condition, not sufficient. If a language satisfies it, it might be regular. If it fails, it's definitely not regular.

Why Pumping Lemma Matters

Non-regularity proofs: Primary tool. DFA limits: Shows finite memory can't count. Intuition: Pigeonhole principle. CFL version: Extends to context-free. Theory: Foundation of formal languages. Practice: Understand regex limits.

📌 Non-regular proofs📌 Pigeonhole📌 Necessary condition📌 Contradiction

# Pumping Lemma — the big picture
print("""
=== The Big Idea ===

Imagine a DFA with p states (p = pumping length).

If you feed it a string longer than p characters,
the DFA MUST visit some state twice (pigeonhole principle).

This creates a LOOP in the state sequence:

  q0 → q1 → ... → qa → ... → qa → ... → qf
                     ↑_______↓
                      loop!

The loop can be:
  - Repeated 0 times (remove the loop)
  - Repeated 1 time (original string)
  - Repeated 2+ times (pump more)

All these strings must be accepted (if original is accepted).

=== What This Means ===

If a language requires "counting" beyond a fixed limit,
it CANNOT be regular.

Example: L = { a^n b^n | n ≥ 0 }
  - Requires matching number of a's and b's
  - No finite memory can count to infinity
  - Therefore NOT regular

The pumping lemma formalizes this intuition.
""")

# ANALOGY
print("=== Analogy: The Hotel with Finite Rooms ===")
print("""
Think of a DFA as a hotel with p rooms (states).

A guest (input string) walks through rooms:
  - Enters room q0
  - Moves to next room based on each character
  - If the path is longer than p rooms,
    they MUST revisit some room.

Once they revisit a room, they're in a loop.
They can go around the loop:
  - 0 times
  - 1 time
  - Any number of times

The hotel manager (DFA) can't tell the difference
between 1 loop and 100 loops — same rooms, same result!

This is why regular languages can't count.
""")

# REAL-LIFE EXAMPLE
print("=== Real-Life Example: Elevator ===")
print("""
An elevator with 3 floors:
  States: {Floor1, Floor2, Floor3}
  Input: floor requests

If you press: 1, 2, 3, 1, 2, 3, 1, 2, 3, ...
The elevator visits Floor1 → Floor2 → Floor3 → Floor1 → ...

The sequence "1, 2, 3" repeats.
Once you've seen the pattern, you know it repeats.

The elevator (DFA) can't count how many times
it has gone around the loop — it just knows the floor.

This is the essence of the pumping lemma.
""")

# WHY IT'S CALLED "PUMPING"
print("=== Why 'Pumping'? ===")
print("""
The middle part (the loop) can be "pumped":
  - Pumped up: repeat it more times
  - Pumped down: repeat it fewer times (even 0)

If w = xyz is in the language,
then xy^k z is in the language for ALL k ≥ 0.

The "pump" is the y part — you can inflate or deflate it.

Example: L = a*b*
  w = "aaabbb"
  x = "aa", y = "a", z = "bbb"
  Pump: "aa" + "a"*k + "bbb"
    k=0: "aabbb"  ✓
    k=1: "aaabbb" ✓
    k=2: "aaaabbb" ✓
    ... all valid!

This works because a*b* doesn't require counting.
""")

📘 Regular Pumping Lemma

🎯 Formal Statement

If L is a regular language, then there exists a pumping length p ≥ 1 such that for every string w ∈ L with |w| ≥ p, there exists a decomposition w = xyz satisfying:

|xy| ≤ p — the loop starts within the first p characters
|y| ≥ 1 — the loop is non-empty (y is not ε)
xy^kz ∈ L for all k ≥ 0 — pumping y any number of times

The Three Conditions

|xy| ≤ p: The loop must occur early (within first p chars). |y| ≥ 1: The loop must consume at least one character. xy^kz ∈ L: Pumping y preserves membership. Contrapositive: If no such decomposition exists, L is NOT regular. Necessary: All regular languages satisfy it. Not sufficient: Some non-regular languages also satisfy it.

|xy| ≤ p|y| ≥ 1xy^kz ∈ Lk ≥ 0

# Regular Pumping Lemma — formal statement
print("""
=== Formal Statement ===

If L is regular, then:
  ∃ p ≥ 1 (pumping length)
  ∀ w ∈ L with |w| ≥ p
    ∃ decomposition w = xyz such that:
      1. |xy| ≤ p
      2. |y| ≥ 1
      3. ∀ k ≥ 0: xy^k z ∈ L

=== Contrapositive (for proving non-regularity) ===

If L is NOT regular, then:
  ∀ p ≥ 1
  ∃ w ∈ L with |w| ≥ p
    ∀ decomposition w = xyz with |xy| ≤ p and |y| ≥ 1:
      ∃ k ≥ 0: xy^k z ∉ L

This is the form we use for proofs!
""")

# VISUAL REPRESENTATION
print("=== Visual Representation ===")
print("""
String w = x y z
          |___|___|___|
          |   |   |
          |   |   └── Suffix (can be anything)
          |   └────── Loop (pump this!)
          └────────── Prefix (within first p chars)

Constraints:
  |xy| ≤ p  — x and y together at most p chars
  |y| ≥ 1   — y has at least 1 char

Pumping:
  k=0:  x z           (remove loop)
  k=1:  x y z         (original)
  k=2:  x y y z       (duplicate loop)
  k=3:  x y y y z     (triple loop)
  ...

All must be in L!
""")

# DFA STATE TRACE
print("=== DFA State Trace ===")
print("""
A DFA with p states processing w (|w| ≥ p):

States visited: q0, q1, q2, ..., qp (p+1 states for p chars)

By pigeonhole principle, some state repeats:
  q0 → q1 → ... → qi → ... → qi → ... → qf
                   |_________|
                    the loop

The loop corresponds to substring y.
  x = string that gets from q0 to qi
  y = string that gets from qi back to qi
  z = string that gets from qi to qf

Since the loop returns to the same state:
  - Removing y: still ends at qf (accept)
  - Adding more y: still loops back to qi, then to qf
  - So xy^k z is accepted for ALL k ≥ 0!

This is why the lemma holds.
""")

# PYTHON IMPLEMENTATION — SIMULATING THE PROOF
print("=== Python: Simulating the Lemma ===")

class DFA:
    """Simple DFA for demonstration."""
    def __init__(self, states, alphabet, delta, q0, F):
        self.Q = states
        self.Sigma = alphabet
        self.delta = delta
        self.q0 = q0
        self.F = F
    
    def accepts(self, word):
        state = self.q0
        for symbol in word:
            state = self.delta[(state, symbol)]
        return state in self.F
    
    def state_trace(self, word):
        """Return sequence of states visited."""
        states = [self.q0]
        state = self.q0
        for symbol in word:
            state = self.delta[(state, symbol)]
            states.append(state)
        return states

def find_pumping_decomposition(dfa, word):
    """
    Find a pumping decomposition for a word in a DFA.
    Returns (x, y, z) or None if word too short.
    """
    p = len(dfa.Q)  # pumping length = number of states
    
    if len(word) < p:
        return None  # too short to pump
    
    # Trace states for first p+1 steps
    trace = dfa.state_trace(word[:p+1])
    
    # Find repeated state
    seen = {}
    for i, state in enumerate(trace):
        if state in seen:
            # Found loop: y = word[seen[state]:i]
            x = word[:seen[state]]
            y = word[seen[state]:i]
            z = word[i:]
            return (x, y, z)
        seen[state] = i
    
    return None  # should never happen if |word| ≥ p

# Example DFA: strings ending in "ab"
dfa = DFA(
    states={'q0', 'q1', 'q2'},
    alphabet={'a', 'b'},
    delta={
        ('q0', 'a'): 'q1',
        ('q0', 'b'): 'q0',
        ('q1', 'a'): 'q1',
        ('q1', 'b'): 'q2',
        ('q2', 'a'): 'q1',
        ('q2', 'b'): 'q0',
    },
    q0='q0',
    F={'q2'}
)

# Test
word = "aabab"
print(f"DFA states: {len(dfa.Q)} (pumping length p = {len(dfa.Q)})")
print(f"Word: {word}")
print(f"Accepted: {dfa.accepts(word)}")

decomp = find_pumping_decomposition(dfa, word)
if decomp:
    x, y, z = decomp
    print(f"\nPumping decomposition:")
    print(f"  x = '{x}'")
    print(f"  y = '{y}'")
    print(f"  z = '{z}'")
    print(f"  |xy| = {len(x)+len(y)} ≤ p = {len(dfa.Q)} ✓")
    print(f"  |y| = {len(y)} ≥ 1 ✓")
    
    print(f"\nPumping y:")
    for k in range(5):
        pumped = x + y*k + z
        accepted = dfa.accepts(pumped)
        print(f"  k={k}: '{pumped}' → {'✓ ACCEPT' if accepted else '✗ REJECT'}")

# THE LEMMA IN ACTION
print("""
=== The Lemma in Action ===

For any regular language L, the pumping lemma holds.

For the DFA above (3 states):
  - Pumping length p = 3
  - Any word of length ≥ 3 can be pumped
  - The loop is within the first 3 chars

For word "aabab":
  x = "a", y = "ab", z = "ab"
  Pump y: "a" + "ab"*k + "ab"
    k=0: "aab"    — is this in L? 
    k=1: "aabab"  — original ✓
    k=2: "aababab" — ✓
  
  Wait — "aab" doesn't end in "ab"! It ends in "ab"?
  "aab" ends in "ab" ✓ (a-a-b, last two are "ab")
  
  All should be accepted!
""")

🔍 Proof & Intuition

🎯 Why Does the Pumping Lemma Work?

The proof relies on the pigeonhole principle: a DFA with p states processing a string longer than p must visit some state twice, creating a loop that can be pumped.

The Pigeonhole Principle

States: p states in DFA. Path: |w|+1 states visited. Pigeonhole: If |w| ≥ p, some state repeats. Loop: The repeated state creates a cycle. Pumping: The cycle can be traversed any number of times. Result: All pumped strings accepted.

🕊️ Pigeonhole🔄 Loop📊 States✅ Pump

# Proof of the Regular Pumping Lemma
print("""
=== Theorem ===
If L is regular, then the pumping lemma holds.

=== Proof ===

Let L be regular.
Then there exists a DFA M = (Q, Σ, δ, q0, F) that accepts L.
Let p = |Q| (number of states).

Take any w ∈ L with |w| ≥ p.
Write w = a₁a₂...aₙ where n = |w| ≥ p.

Consider the sequence of states visited:
  q0, q1, q2, ..., qn
where qᵢ = δ*(q0, a₁...aᵢ).

This sequence has n+1 states.
Since n ≥ p, we have n+1 > p = |Q|.

By the PIGEONHOLE PRINCIPLE,
there exist indices i < j such that qᵢ = qⱼ
with 0 ≤ i < j ≤ p (since we only need first p+1 states).

Now define:
  x = a₁...aᵢ       (prefix)
  y = aᵢ₊₁...aⱼ     (loop)
  z = aⱼ₊₁...aₙ     (suffix)

Then w = xyz.

Properties:
  1. |xy| = j ≤ p  ✓ (since j ≤ p)
  2. |y| = j - i ≥ 1  ✓ (since i < j)
  3. For any k ≥ 0:
     δ*(q0, xy^k z)
     = δ*(δ*(q0, x), y^k z)
     = δ*(qᵢ, y^k z)        [since δ*(q0, x) = qᵢ]
     = δ*(qᵢ, y^k) then z
     = δ*(qᵢ, z)            [since y loops qᵢ → qᵢ]
     = δ*(q0, xyz)          [since x gets to qᵢ]
     = δ*(q0, w)            [since w = xyz]
     ∈ F                    [since w ∈ L]
     
     So xy^k z ∈ L for all k ≥ 0.  ∎

=== Key Insight ===

The loop y starts and ends at the same state qᵢ.
Traversing it any number of times doesn't change the state.
So the final state (and acceptance) is unchanged.
""")

# VISUAL PROOF
print("=== Visual Proof ===")
print("""
DFA with states q0, q1, q2 (p = 3)
Input: w = "aabab" (|w| = 5 ≥ 3)

State trace:
  Start: q0
  Read 'a' → q1
  Read 'a' → q1     ← q1 repeats!
  Read 'b' → q2
  Read 'a' → q1
  Read 'b' → q2

Sequence: q0, q1, q1, q2, q1, q2
                ↑___↑
                loop!

The loop is at q1 (positions 1 to 2 in the trace).
  x = "a"     (gets from q0 to q1)
  y = "a"     (loops q1 back to q1)
  z = "bab"   (gets from q1 to q2)

Wait — this doesn't match our earlier decomposition.
The lemma allows ANY valid decomposition.
Both "a"+"a"+"bab" and "a"+"ab"+"ab" work.

Let's verify: x="a", y="a", z="bab"
  k=0: "abab"   — ends in "ab" ✓
  k=1: "aabab"  — original ✓
  k=2: "aaabab" — ends in "ab" ✓

All accepted! The lemma holds.
""")

# PIGEONHOLE ILLUSTRATION
print("=== Pigeonhole Principle ===")
print("""
Pigeons (states visited) > Pigeonholes (DFA states)
→ Some pigeonhole has 2+ pigeons
→ Some state is visited 2+ times

Example with 3 states and 5 characters:
  States: [A, B, C]
  Path:   A → B → B → C → B → C
                ↑___↑
                B repeats!

There are 6 state visits but only 3 states.
So at least one state repeats.

The repeated state creates a cycle.
The cycle can be pumped.
""")

# FORMAL PROOF IN CODE
print("=== Formal Proof in Code ===")

def prove_pumping_lemma(dfa, word):
    """
    Constructively prove the pumping lemma for a specific DFA and word.
    Returns the decomposition and verification.
    """
    p = len(dfa.Q)
    
    if len(word) < p:
        return None, "Word too short"
    
    if not dfa.accepts(word):
        return None, "Word not in language"
    
    # Trace states
    trace = dfa.state_trace(word)
    
    # Find first repeated state in first p+1 states
    seen = {}
    for i in range(min(len(trace), p + 1)):
        state = trace[i]
        if state in seen:
            j = i
            i_orig = seen[state]
            
            x = word[:i_orig]
            y = word[i_orig:j]
            z = word[j:]
            
            # Verify conditions
            conditions = {
                'w = xyz': x + y + z == word,
                '|xy| ≤ p': len(x) + len(y) <= p,
                '|y| ≥ 1': len(y) >= 1,
            }
            
            # Verify pumping
            pumped = []
            for k in range(5):
                xyzk = x + y*k + z
                pumped.append((k, xyzk, dfa.accepts(xyzk)))
            
            return (x, y, z), conditions, pumped
        seen[state] = i
    
    return None, "No repeat found (shouldn't happen)"

# Test on different DFA
dfa2 = DFA(
    states={'s0', 's1', 's2', 's3'},
    alphabet={'a', 'b'},
    delta={
        ('s0', 'a'): 's1',
        ('s0', 'b'): 's0',
        ('s1', 'a'): 's1',
        ('s1', 'b'): 's2',
        ('s2', 'a'): 's1',
        ('s2', 'b'): 's3',
        ('s3', 'a'): 's1',
        ('s3', 'b'): 's0',
    },
    q0='s0',
    F={'s3'}
)

words = ['abb', 'aabb', 'abbb', 'aaabbb']
print(f"DFA with {len(dfa2.Q)} states (p = {len(dfa2.Q)})")
print(f"Language: strings ending in 'abb'\n")

for w in words:
    result = prove_pumping_lemma(dfa2, w)
    if result[0]:
        x, y, z = result[0]
        conditions, pumped = result[1], result[2]
        print(f"Word: '{w}'")
        print(f"  Decomposition: x='{x}', y='{y}', z='{z}'")
        for cond, val in conditions.items():
            print(f"  {cond}: {val}")
        print(f"  Pumping:")
        for k, xyzk, accepted in pumped:
            print(f"    k={k}: '{xyzk}' → {'✓' if accepted else '✗'}")
        print()
    else:
        print(f"Word: '{w}' — {result[1]}\n")

# WHY IT'S NECESSARY BUT NOT SUFFICIENT
print("""
=== Necessary but NOT Sufficient ===

The pumping lemma is a NECESSARY condition:
  If L is regular → pumping lemma holds.
  
The CONTRAPOSITIVE is what we use:
  If pumping lemma fails → L is NOT regular.

BUT the converse is NOT true:
  Pumping lemma holds ⇏ L is regular.

There exist NON-regular languages that satisfy
the pumping lemma! (But they fail more general
versions like Ogden's lemma.)

This is a common trap in proofs.
Always remember: the pumping lemma can only
DISPROVE regularity, never PROVE it.
""")

📝 Proof Method (Game)

🎯 The Adversarial Game

Proving a language is not regular is like a game against an adversary. You must show that no matter what pumping length the adversary picks, you can find a string that fails to pump.

The Game Rules

1. Adversary: Picks pumping length p. 2. You: Choose a string w ∈ L with |w| ≥ p. 3. Adversary: Splits w = xyz with |xy| ≤ p, |y| ≥ 1. 4. You: Choose k ≥ 0 such that xy^kz ∉ L. 5. You win: If you can always do this, L is not regular.

🎮 Adversary📝 Choose w✂️ Split💥 Pump

# The Pumping Lemma Game — proof method
print("""
=== The Game (Adversarial Proof) ===

To prove L is NOT regular:

ROUND 1: Adversary picks p ≥ 1
  (You don't know p, must work for ALL p)

ROUND 2: You pick w ∈ L with |w| ≥ p
  (Clever choice — often uses p as a parameter)

ROUND 3: Adversary splits w = xyz with |xy| ≤ p, |y| ≥ 1
  (You don't control the split)

ROUND 4: You pick k ≥ 0 such that xy^k z ∉ L
  (Usually k = 0 or k = 2)

WIN: If you can always win, L is NOT regular.
""")

# STEP-BY-STEP TEMPLATE
print("=== Proof Template ===")
print("""
Claim: L is not regular.

Proof (by contradiction):
  Assume L is regular.
  Let p be the pumping length guaranteed by the lemma.

  Choose w = _______________ ∈ L with |w| ≥ p.
  (Often w uses p, e.g., a^p b^p)

  By the pumping lemma, w = xyz where:
    - |xy| ≤ p
    - |y| ≥ 1

  Consider cases for y:
    Case 1: y contains only a's
    Case 2: y contains only b's
    Case 3: y contains both a's and b's
    (Cover all possibilities based on |xy| ≤ p)

  In each case, choose k = ___ (usually 0 or 2).
  Show xy^k z ∉ L.
  (Usually because it violates the counting/balance)

  Contradiction!
  Therefore L is NOT regular.  ∎
""")

# EXAMPLE 1: a^n b^n
print("=== Example 1: L = { a^n b^n | n ≥ 0 } ===")
print("""
Proof:
  Assume L is regular with pumping length p.
  
  Choose w = a^p b^p ∈ L.  (|w| = 2p ≥ p ✓)
  
  By pumping lemma, w = xyz with |xy| ≤ p, |y| ≥ 1.
  
  Since |xy| ≤ p, xy consists only of a's (first p chars are a's).
  So y = a^m for some m ≥ 1.
  
  Now consider xy^0 z = xz:
    xz = a^(p-m) b^p
    
  This has p-m a's and p b's.
  Since m ≥ 1, p-m < p.
  So xz has UNEQUAL numbers of a's and b's.
  Therefore xz ∉ L.
  
  Contradiction!  Therefore L is NOT regular.  ∎
""")

# EXAMPLE 2: a^n b^n c^n
print("=== Example 2: L = { a^n b^n c^n | n ≥ 0 } ===")
print("""
Proof:
  Assume L is regular with pumping length p.
  
  Choose w = a^p b^p c^p ∈ L.
  
  By pumping lemma, w = xyz with |xy| ≤ p, |y| ≥ 1.
  
  Since |xy| ≤ p, y consists only of a's.
  So y = a^m for m ≥ 1.
  
  Consider xy^2 z = x y y z:
    This has p+m a's, p b's, p c's.
    More a's than b's or c's.
    So xy^2 z ∉ L.
  
  Contradiction!  L is NOT regular.  ∎
""")

# EXAMPLE 3: Palindromes
print("=== Example 3: L = { w | w = w^R } (palindromes) ===")
print("""
Proof:
  Assume L is regular with pumping length p.
  
  Choose w = a^p b a^p ∈ L.  (palindrome: a...a b a...a)
  
  By pumping lemma, w = xyz with |xy| ≤ p, |y| ≥ 1.
  
  Since |xy| ≤ p, y consists only of a's (from the first a^p).
  So y = a^m for m ≥ 1.
  
  Consider xy^0 z = xz:
    xz = a^(p-m) b a^p
    
  Is this a palindrome?
    First half: a^(p-m) b ...
    Last half: ... b a^p
    For palindrome, need p-m = p, i.e., m = 0.
    But m ≥ 1. Contradiction!
  
  So xz ∉ L.  Therefore L is NOT regular.  ∎
""")

# COMMON STRING CHOICES
print("=== Common String Choices ===")
print("""
For different languages, choose w strategically:

L = { a^n b^n }        → w = a^p b^p
L = { a^n b^n c^n }    → w = a^p b^p c^p
L = { a^n b^m, n > m } → w = a^(p+1) b^p
L = { w w }            → w = a^p b a^p b
L = { w w^R }          → w = a^p b a^p
L = { a^(n^2) }        → w = a^(p^2)
L = { a^p, p prime }   → w = a^q where q ≥ p prime

Rule: Make w long enough that any split y
      is "inside" a single repeated character block.
""")

# INTERACTIVE GAME
print("=== Interactive Proof Game ===")

def play_pumping_game(language_name, chooser, splitter, pump_chooser, max_p=10):
    """
    Simulate the pumping lemma game.
    
    chooser: function(p) → w (your choice of string)
    splitter: function(w, p) → (x, y, z) (adversary's split)
    pump_chooser: function(x, y, z) → k (your pump choice)
    """
    print(f"\n=== Game: {language_name} ===")
    
    for p in range(1, max_p + 1):
        print(f"\nAdversary picks p = {p}")
        
        # You choose w
        w = chooser(p)
        print(f"  You choose w = '{w}'")
        
        if len(w) < p:
            print(f"  ✗ w too short! (|w| = {len(w)} < p = {p})")
            continue
        
        # Adversary splits
        x, y, z = splitter(w, p)
        print(f"  Adversary splits: x='{x}', y='{y}', z='{z}'")
        
        # Verify adversary's split is valid
        if len(x) + len(y) > p:
            print(f"  ✗ Invalid split: |xy| = {len(x)+len(y)} > p")
            continue
        if len(y) < 1:
            print(f"  ✗ Invalid split: |y| = {len(y)} < 1")
            continue
        
        # You choose k
        k = pump_chooser(x, y, z)
        pumped = x + y*k + z
        print(f"  You choose k = {k}: xy^k z = '{pumped}'")
        
        # Check if pumped string is in language
        # (This is language-specific — we'll just report)
        print(f"  → Is '{pumped}' in L? (depends on language)")
    
    print(f"\nIf you can always find such k, {language_name} is NOT regular!")

# Example: a^n b^n
print("\n--- Playing with a^n b^n ---")

def choose_w(p):
    return 'a' * p + 'b' * p

def split_w(w, p):
    # Adversary must split with |xy| ≤ p and |y| ≥ 1
    # Since first p chars are a's, y is all a's
    i = p - 1  # x + y ends at position p-1
    j = p      # y ends at position p
    return w[:i], w[i:j], w[j:]

def choose_k(x, y, z):
    return 0  # remove the a's — creates imbalance

play_pumping_game(
    "a^n b^n",
    choose_w,
    split_w,
    choose_k,
    max_p=5
)

# PROOF WRITING TIPS
print("\n=== Proof Writing Tips ===")
print("""
1. STATE THE CONTRADICTION
   "Assume L is regular. Let p be the pumping length."

2. CHOOSE W CAREFULLY
   Use p in your string. Usually a^p b^p or similar.

3. CONSIDER ALL SPLITS
   The adversary controls the split.
   You must handle EVERY possible split.
   Use |xy| ≤ p to constrain possibilities.

4. CHOOSE K WISELY
   Usually k = 0 (remove y) or k = 2 (double y).
   Pick the one that breaks the language property.

5. SHOW CONTRADICTION
   "But xy^k z ∉ L, contradicting the pumping lemma."

6. CONCLUDE
   "Therefore L is NOT regular. ∎"

7. BE RIGOROUS
   - Justify |xy| ≤ p
   - Justify |y| ≥ 1
   - Show xy^k z ∉ L explicitly
""")

🎯 Classic Examples

🎯 Non-Regular Languages

These languages are not regular and are proved so using the pumping lemma. They're classics in automata theory.

Classic Non-Regular Languages

aⁿbⁿ: Requires counting. aⁿbⁿcⁿ: Three-way counting. Palindromes: Requires full memory. ww: Requires copying. Primes: Number-theoretic. Squares: a^n².

🔢 Counting🪞 Palindromes📋 Copying🔢 Primes

# Classic non-regular languages with proofs
print("=" * 60)
print("CLASSIC NON-REGULAR LANGUAGES")
print("=" * 60)

# 1. a^n b^n
print("""
=== 1. L₁ = { aⁿbⁿ | n ≥ 0 } ===

Intuition: Need to count a's and match with b's.
No finite memory can count arbitrarily high.

PROOF:
  Assume L₁ regular with pumping length p.
  Choose w = aᵖbᵖ ∈ L₁.
  By pumping lemma: w = xyz, |xy| ≤ p, |y| ≥ 1.
  Since |xy| ≤ p, y = aᵐ for some m ≥ 1.
  
  Take k = 0: xy⁰z = xz = aᵖ⁻ᵐbᵖ.
  This has p-m a's and p b's.
  Since m ≥ 1, p-m ≠ p.
  So xz ∉ L₁.
  Contradiction. ∎
""")

# 2. a^n b^n c^n
print("""
=== 2. L₂ = { aⁿbⁿcⁿ | n ≥ 0 } ===

Intuition: Three-way counting — even harder.

PROOF:
  Assume L₂ regular with pumping length p.
  Choose w = aᵖbᵖcᵖ ∈ L₂.
  By pumping lemma: w = xyz, |xy| ≤ p, |y| ≥ 1.
  Since |xy| ≤ p, y = aᵐ for some m ≥ 1.
  
  Take k = 2: xy²z = aᵖ⁺ᵐbᵖcᵖ.
  This has p+m a's, p b's, p c's.
  Unequal counts → not in L₂.
  Contradiction. ∎
""")

# 3. Palindromes
print("""
=== 3. L₃ = { w ∈ {a,b}* | w = wᴿ } ===

Intuition: Need to remember the first half to match the second.

PROOF:
  Assume L₃ regular with pumping length p.
  Choose w = aᵖbaᵖ ∈ L₃ (palindrome).
  By pumping lemma: w = xyz, |xy| ≤ p, |y| ≥ 1.
  Since |xy| ≤ p, y = aᵐ for some m ≥ 1.
  
  Take k = 0: xz = aᵖ⁻ᵐbaᵖ.
  For palindrome: first half must equal reverse of second.
  aᵖ⁻ᵐb... vs ...baᵖ
  Need p-m = p, so m = 0. But m ≥ 1.
  xz ∉ L₃.
  Contradiction. ∎
""")

# 4. ww
print("""
=== 4. L₄ = { ww | w ∈ {a,b}* } ===

Intuition: Need to remember entire first half.

PROOF:
  Assume L₄ regular with pumping length p.
  Choose w = aᵖbaᵖb ∈ L₄ (w = aᵖb, so ww = aᵖbaᵖb).
  By pumping lemma: w = xyz, |xy| ≤ p, |y| ≥ 1.
  Since |xy| ≤ p, y = aᵐ for some m ≥ 1.
  
  Take k = 0: xz = aᵖ⁻ᵐbaᵖb.
  For this to be in L₄ = {ww}, it must split
  into two equal halves.
  Length = 2p - m + 1 (odd if m is even...)
  Actually length = (p-m) + 1 + p + 1 = 2p - m + 2.
  Half length = p - m/2 + 1.
  The first half would end inside the second a-block.
  Not equal to second half.
  xz ∉ L₄.
  Contradiction. ∎
""")

# 5. a^(n^2)
print("""
=== 5. L₅ = { aⁿ² | n ≥ 0 } ===

Intuition: Gap between consecutive squares grows.

PROOF:
  Assume L₅ regular with pumping length p.
  Choose w = aᵖ² ∈ L₅.
  By pumping lemma: w = xyz, |xy| ≤ p, |y| ≥ 1.
  Let |y| = m where 1 ≤ m ≤ p.
  
  Consider xy²z: length = p² + m.
  We need p² + m to be a perfect square.
  But p² < p² + m ≤ p² + p < (p+1)² = p² + 2p + 1.
  
  The next perfect square after p² is (p+1)².
  Since m ≤ p < 2p+1, p² + m is strictly between
  p² and (p+1)², so NOT a perfect square.
  
  xy²z ∉ L₅.
  Contradiction. ∎
""")

# 6. Primes
print("""
=== 6. L₆ = { aᵖ | p is prime } ===

Intuition: Primes have no simple pattern.

PROOF:
  Assume L₆ regular with pumping length p.
  Choose w = a^q where q is prime and q ≥ p.
  (Such q exists by Euclid's theorem.)
  
  By pumping lemma: w = xyz, |xy| ≤ p, |y| ≥ 1.
  Let |y| = m where 1 ≤ m ≤ p.
  
  Consider xy^(q+1)z: length = q + q·m = q(1+m).
  Wait — that's not right.
  
  Actually: |xy^k z| = |x| + k|y| + |z|
           = (|x|+|y|+|z|) + (k-1)|y|
           = q + (k-1)m
  
  Choose k = q+1: length = q + q·m = q(m+1).
  This is composite (divisible by q).
  So xy^(q+1)z ∉ L₆.
  Contradiction. ∎
""")

# 7. More examples
print("""
=== 7. L₇ = { aⁱbʲ | i > j } ===

PROOF:
  Assume L₇ regular with pumping length p.
  Choose w = aᵖ⁺¹bᵖ ∈ L₇.
  By pumping: w = xyz, |xy| ≤ p, |y| ≥ 1.
  y = aᵐ for some m ≥ 1.
  
  Take k = 0: xz = aᵖ⁺¹⁻ᵐbᵖ.
  a count: p+1-m, b count: p.
  For a > b: need p+1-m > p, i.e., 1 > m.
  But m ≥ 1. So a ≤ b. xz ∉ L₇.
  Contradiction. ∎

=== 8. L₈ = { aⁱbʲcᵏ | i = j or j = k } ===

Tricky! This IS regular? No, it's not.
But pumping lemma is harder here.

Actually L₈ is not regular, but the proof
requires more careful case analysis.

Better approach: Use closure properties.
  L₈ ∩ a*b*c* = { aⁱbʲcᵏ | i=j or j=k }
  If L₈ were regular, this would be too.
  But aⁱbⁱc* ∪ a*bⁱcⁱ is not regular.
  (Intersection with aⁱbⁱcⁱ gives aⁱbⁱcⁱ
   which we know is not regular.)
""")

# TABLE OF EXAMPLES
print("=== Summary Table ===")
print(f"{'Language':<30} {'Not Regular?':<15} {'Pumping String':<20}")
print("-" * 65)
print(f"{'aⁿbⁿ':<30} {'Yes':<15} {'aᵖbᵖ':<20}")
print(f"{'aⁿbⁿcⁿ':<30} {'Yes':<15} {'aᵖbᵖcᵖ':<20}")
print(f"{'ww':<30} {'Yes':<15} {'aᵖbaᵖb':<20}")
print(f"{'w = wᴿ (palindromes)':<30} {'Yes':<15} {'aᵖbaᵖ':<20}")
print(f"{'aⁿ²':<30} {'Yes':<15} {'aᵖ²':<20}")
print(f"{'aᵖ (prime)':<30} {'Yes':<15} {'a^q (prime)':<20}")
print(f"{'aⁱbʲ, i > j':<30} {'Yes':<15} {'aᵖ⁺¹bᵖ':<20}")
print(f"{'aⁱbʲ, i ≤ j':<30} {'Yes':<15} {'aᵖbᵖ⁺¹':<20}")
print(f"{'a*b* (regular)':<30} {'No (is regular)':<15} {'N/A':<20}")
print(f"{'(ab)* (regular)':<30} {'No (is regular)':<15} {'N/A':<20}")

# DETAILED CASE ANALYSIS EXAMPLE
print("=== Detailed Case Analysis: L = { aⁱbʲ | i ≠ j } ===")
print("""
This language is actually NOT regular.
Proof:

Assume L is regular with pumping length p.
Choose w = aᵖbᵖ⁺¹ ∈ L (since p ≠ p+1).

By pumping lemma: w = xyz, |xy| ≤ p, |y| ≥ 1.

Since |xy| ≤ p and first p chars are a's,
y must be aᵐ for some 1 ≤ m ≤ p.

Consider k = 0: xz = aᵖ⁻ᵐbᵖ⁺¹.
  a count: p-m, b count: p+1.
  Since m ≤ p, p-m ≥ 0.
  Are they equal? p-m = p+1? → -m = 1 → m = -1. No.
  So p-m ≠ p+1 for all m ≥ 1.
  Wait — we need i ≠ j for acceptance.
  p-m vs p+1: p-m < p+1 always (since m ≥ 1).
  So they're unequal → xz ∈ L!

Hmm, that doesn't work. Let's try k = 2:
xy²z = aᵖ⁺ᵐbᵖ⁺¹.
  a count: p+m, b count: p+1.
  Are they equal? p+m = p+1 → m = 1.
  If m = 1, they're equal → not in L!
  If m > 1, p+m > p+1 → not equal → in L.
  
  Problem: adversary might choose m = 1.

We need a better string. Let's use w = aᵖbᵖ⁺¹.
  Actually, let's use w = aᵖbᵖ⁻¹ (with p ≥ 2).
  
  Wait — need i ≠ j. aᵖbᵖ⁻¹ has p ≠ p-1 ✓.
  
  By pumping: y = aᵐ, 1 ≤ m ≤ p.
  Take k = 0: xz = aᵖ⁻ᵐbᵖ⁻¹.
    a count: p-m, b count: p-1.
    Equal? p-m = p-1 → m = 1.
    If m = 1, equal → xz ∉ L ✓ (we want this!)
    If m > 1, unequal → xz ∈ L ✗
  
  Adversary chooses m > 1 to avoid our k=0.
  
  Try k = 2: xy²z = aᵖ⁺ᵐbᵖ⁻¹.
    Equal? p+m = p-1 → m = -1. No.
    So always unequal → in L. ✗
  
  Hmm, this is tricky! The language { aⁱbʲ | i ≠ j }
  IS regular? Let's check...
  
  Actually, { aⁱbʲ | i ≠ j } is the complement of
  { aⁱbʲ | i = j } within a*b*.
  
  { aⁱbʲ | i = j } = aⁿbⁿ is NOT regular.
  But complement of a non-regular language
  within a regular set is not necessarily non-regular!
  
  Wait — a*b* is regular.
  { aⁿbⁿ } is not regular.
  a*b* \ { aⁿbⁿ } = { aⁱbʲ | i ≠ j }.
  
  Is this regular? Let's think...
  
  A DFA can check i ≠ j by:
    - Count a's (mod something?) — no, need exact
    - Actually, can a DFA check i ≠ j?
    
  No! Because to know i ≠ j, you need to compare
  the count of a's with count of b's.
  That requires unbounded memory.
  
  So { aⁱbʲ | i ≠ j } is NOT regular.
  
  But the pumping lemma proof is subtle!
  (It's a known tricky example.)
  
  Correct proof uses w = aᵖbᵖ⁺ᵖ! (much longer)
  Or uses closure properties.
""")

⚠️ Common Mistakes

🎯 Pitfalls in Pumping Lemma Proofs

The pumping lemma is easy to misuse. Here are the most common mistakes and how to avoid them.

Top Mistakes

1. Wrong direction: Using it to prove regularity. 2. Choosing w poorly: Must work for all p. 3. Ignoring splits: Must handle all decompositions. 4. Wrong k: Must show xy^kz ∉ L. 5. Assuming split: Can't choose x, y, z. 6. Forgetting |xy|≤p.

⚠️ Direction⚠️ All splits⚠️ All p⚠️ Valid k

# Common Mistakes in Pumping Lemma Proofs
print("=" * 60)
print("COMMON MISTAKES")
print("=" * 60)

# MISTAKE 1: Using it to prove regularity
print("""
=== MISTAKE 1: Proving Regularity ===

WRONG:
  "L satisfies the pumping lemma, so L is regular."
  
WRONG because:
  The pumping lemma is NECESSARY, not SUFFICIENT.
  Some non-regular languages also satisfy it.

CORRECT:
  "L fails the pumping lemma, so L is NOT regular."
  (Contrapositive is valid.)
  
  "L satisfies the pumping lemma" tells you NOTHING
  about whether L is regular.

Example of non-regular language that satisfies
the pumping lemma:
  L = { aⁱbʲcᵏ | i=1 ⟹ j=k }
  This satisfies pumping lemma but is not regular.
""")

# MISTAKE 2: Choosing w that depends on the split
print("""
=== MISTAKE 2: Choosing w After Seeing the Split ===

WRONG:
  "Adversary picks p, I pick w = aᵖbᵖ.
   Adversary splits w = xyz.
   Oh wait, y might be 'ab', so let me pick w = aᵖbᵖ⁺¹ instead."
  
WRONG because:
  You must choose w BEFORE the adversary splits.
  Your w must work for EVERY possible valid split.

CORRECT:
  Choose w once, based on p.
  Then handle ALL possible splits in your proof.
  Use cases: y is all a's, y is all b's, y is mixed, etc.
""")

# MISTAKE 3: Not considering all splits
print("""
=== MISTAKE 3: Only Considering One Split ===

WRONG:
  "w = aᵖbᵖ. Since |xy| ≤ p, y = aᵐ.
   Then xz = aᵖ⁻ᵐbᵖ ∉ L. Done."
  
WRONG if there are other possible splits!
  Actually, in this case, since |xy| ≤ p and first p chars
  are a's, y MUST be all a's. So this is correct.
  
But consider w = aᵖbᵖ:
  |xy| ≤ p means xy is within first p chars.
  First p chars are all a's.
  So y is all a's. Only one case!
  
For w = aᵖbᵖcᵖ:
  |xy| ≤ p means xy within first p chars (all a's).
  So y is all a's. Only one case.
  
But for w = aᵖbᵖ⁺¹:
  Same — y is all a's.
  
When do multiple cases arise?
  When w has mixed characters in first p positions.
  E.g., w = (ab)ᵖ — first p chars have a's and b's.
  Then y could be "a", "b", "ab", "ba", etc.

Always enumerate ALL possible y!
""")

# MISTAKE 4: Wrong k
print("""
=== MISTAKE 4: Choosing Wrong k ===

WRONG:
  "Take k = 1: xy¹z = xyz = w ∈ L."
  
WRONG because:
  k = 1 gives back the original string.
  You need to show SOME k makes xy^k z ∉ L.
  Usually k = 0 or k = 2.

CORRECT:
  Choose k = 0 (remove y) or k = 2 (double y).
  Pick the one that breaks the language property.

Example: L = { aⁿbⁿ }
  k = 0: xz = aᵖ⁻ᵐbᵖ — has fewer a's than b's. ∉ L ✓
  k = 2: xy²z = aᵖ⁺ᵐbᵖ — has more a's than b's. ∉ L ✓
  Either works!

Example: L = { ww }
  k = 0: xz has odd length (if m odd) — not a ww. ∉ L
  k = 2: xy²z has wrong structure. ∉ L
""")

# MISTAKE 5: Assuming specific split
print("""
=== MISTAKE 5: Assuming a Specific Split ===

WRONG:
  "Adversary splits w = aᵖbᵖ as x = aᵖ⁻¹, y = a, z = bᵖ."
  
WRONG because:
  The adversary chooses the split!
  You must handle ANY valid split.
  
  Adversary could choose:
    x = ε, y = aᵐ, z = aᵖ⁻ᵐbᵖ  (for any 1 ≤ m ≤ p)
    x = aᵏ, y = aᵐ, z = aᵖ⁻ᵏ⁻ᵐbᵖ
  etc.
  
CORRECT:
  Say "y = aᵐ for some m ≥ 1"
  Then show xy^k z ∉ L for all valid m.
""")

# MISTAKE 6: Forgetting |xy| ≤ p
print("""
=== MISTAKE 6: Forgetting |xy| ≤ p ===

The condition |xy| ≤ p is CRUCIAL.
It ensures y is in the "early" part of the string.

Without it, y could be anywhere, and the proof breaks.

Example: L = { aⁿbⁿ }
  Without |xy| ≤ p, y could be "ab" (if |y| = 2).
  Then xy^0 z would still have equal a's and b's!
  
With |xy| ≤ p:
  y must be all a's (since first p chars are a's).
  Then removing y breaks the balance.

Always use |xy| ≤ p to constrain y!
""")

# MISTAKE 7: Using pumping lemma for regular languages
print("""
=== MISTAKE 7: Wrong Version of the Lemma ===

Don't confuse:
  - Regular pumping lemma (for regular languages)
  - CFL pumping lemma (for context-free languages)

They have DIFFERENT conditions!

Regular: w = xyz, |xy| ≤ p, |y| ≥ 1, xy^k z ∈ L
CFL:     w = uvxyz, |vxy| ≤ p, |vy| ≥ 1, uv^k xy^k z ∈ L

The CFL version pumps TWO parts (v and y) simultaneously.
""")

# MISTAKE 8: Not proving contradiction
print("""
=== MISTAKE 8: Not Completing the Contradiction ===

WRONG:
  "So xy^0 z = aᵖ⁻ᵐbᵖ. This has unequal a's and b's."
  (Stops here — doesn't say "therefore not in L")
  
CORRECT:
  "So xy^0 z = aᵖ⁻ᵐbᵖ.
   This has p-m a's and p b's.
   Since m ≥ 1, p-m < p.
   So xy^0 z has unequal numbers of a's and b's.
   Therefore xy^0 z ∉ L.
   But the pumping lemma says xy^0 z ∈ L.
   CONTRADICTION.
   Therefore L is NOT regular. ∎"
   
Always complete the logical chain!
""")

# CORRECT PROOF TEMPLATE
print("""
=== CORRECT PROOF TEMPLATE ===

Claim: L = { aⁿbⁿ | n ≥ 0 } is not regular.

Proof (by contradiction):
  1. Assume L is regular.
  2. Let p be the pumping length.
  3. Choose w = aᵖbᵖ. (w ∈ L, |w| = 2p ≥ p)
  4. By pumping lemma, w = xyz with:
       |xy| ≤ p
       |y| ≥ 1
       ∀k≥0: xy^k z ∈ L
  5. Since |xy| ≤ p, y consists only of a's.
     So y = aᵐ for some m ≥ 1.
  6. Consider k = 0: xy⁰z = xz = aᵖ⁻ᵐbᵖ.
  7. This has p-m a's and p b's.
  8. Since m ≥ 1, p-m < p, so a's ≠ b's.
  9. Therefore xz ∉ L.
  10. But pumping lemma says xz ∈ L. Contradiction.
  11. Therefore L is NOT regular. ∎
""")

# CHECKLIST
print("=== Proof Checklist ===")
print("""
✓ Assume L is regular
✓ Let p be the pumping length
✓ Choose w ∈ L with |w| ≥ p (using p)
✓ Consider ALL possible splits w = xyz
   with |xy| ≤ p and |y| ≥ 1
✓ For each split, find k ≥ 0 with xy^k z ∉ L
✓ Show explicitly why xy^k z ∉ L
✓ State the contradiction
✓ Conclude L is not regular
✓ Mark end of proof (∎)

Common pitfalls to avoid:
✗ Using pumping lemma to prove regularity
✗ Choosing w after seeing the split
✗ Only considering one split
✗ Using k = 1 (gives original string)
✗ Forgetting |xy| ≤ p
✗ Not completing the contradiction
""")

📗 CFL Pumping Lemma

🎯 Context-Free Pumping Lemma

For context-free languages, there's a similar lemma. If L is a CFL, then sufficiently long strings can be decomposed into five parts uvxyz, where both v and y can be pumped simultaneously.

CFL Pumping Lemma Statement

If L is a CFL: ∃ pumping length p. ∀ w ∈ L: |w| ≥ p. ∃ decomposition: w = uvxyz. |vxy| ≤ p: Middle part bounded. |vy| ≥ 1: At least one non-empty. ∀ k ≥ 0: uv^kxy^kz ∈ L.

uvxyz|vxy| ≤ p|vy| ≥ 1uv^kxy^kz

# CFL Pumping Lemma
print("""
=== CFL Pumping Lemma — Formal Statement ===

If L is a context-free language, then:
  ∃ p ≥ 1 (pumping length)
  ∀ w ∈ L with |w| ≥ p
    ∃ decomposition w = uvxyz such that:
      1. |vxy| ≤ p
      2. |vy| ≥ 1
      3. ∀ k ≥ 0: uv^k xy^k z ∈ L

=== Comparison with Regular Version ===

Regular:  w = xyz,    |xy| ≤ p,   |y| ≥ 1,   xy^k z ∈ L
CFL:      w = uvxyz,  |vxy| ≤ p,  |vy| ≥ 1,  uv^k xy^k z ∈ L

CFL pumps TWO substrings (v and y) simultaneously!

=== Why Two Parts? ===

Context-free languages are generated by CFGs.
A long string in a CFL has a parse tree.
A long path in the parse tree has a repeated nonterminal.
The repeated nonterminal generates v...y (with v and y at the ends).
Both v and y can be pumped together.

This allows CFLs to handle some counting:
  - One counter (like aⁿbⁿ)
  - But not two counters (like aⁿbⁿcⁿ)
""")

# VISUAL REPRESENTATION
print("=== Visual Representation ===")
print("""
String w = u v x y z
          |_|_|_|_|_|
          | | | | |
          | | | | └── Suffix
          | | | └──── Second pumpable part
          | | └────── Middle (not pumped)
          | └──────── First pumpable part
          └────────── Prefix

Constraints:
  |vxy| ≤ p    — v, x, y together at most p chars
  |vy| ≥ 1     — at least one of v, y is non-empty

Pumping:
  k=0:  u z           (remove both v and y)
  k=1:  u v x y z     (original)
  k=2:  u vv x yy z   (double both)
  k=3:  u vvv x yyy z (triple both)
  ...

Both v and y are pumped TOGETHER (same k).
""")

# PARSE TREE INTUITION
print("=== Parse Tree Intuition ===")
print("""
A CFG generates strings via parse trees.

For a long string, the parse tree is tall.
By pigeonhole, some nonterminal repeats on a root-to-leaf path.

  S
  |
  A
  |
  ...
  A      ← same nonterminal repeats!
  |  \\
  v   y  ← these are the pumpable parts
  
  ...

The repeated nonterminal A generates:
  A →* v A y  (with v, y at the ends)

So:
  A →* v A y →* vv A yy →* vvv A yyy →* ...

Pumping v and y together preserves the language!
""")

# EXAMPLE 1: a^n b^n
print("=== Example: L = { aⁿbⁿ | n ≥ 0 } ===")
print("""
This IS a CFL (not regular, but context-free).

Grammar:
  S → aSb | ε

Parse tree for a³b³:
        S
       /|\\
      a S b
       /|\\
      a S b
       /|\\
      a S b
        |
        ε

Pumping: v = a, y = b (or similar)
  uv^k xy^k z keeps a's and b's balanced!
""")

# EXAMPLE 2: a^n b^n c^n — NOT CFL
print("=== Example: L = { aⁿbⁿcⁿ | n ≥ 0 } ===")
print("""
This is NOT context-free!

PROOF using CFL pumping lemma:

Assume L is a CFL with pumping length p.
Choose w = aᵖbᵖcᵖ ∈ L.

By pumping lemma: w = uvxyz with |vxy| ≤ p, |vy| ≥ 1.

Since |vxy| ≤ p, vxy cannot contain all three symbols
(a, b, c). Because that would require at least 3 chars
and spanning from first a to last c, which is > p.

Case analysis:
  Case 1: vxy contains only a's
    Then pumping changes a count only.
    uv²xy²z has more a's than b's or c's. ∉ L.
  Case 2: vxy contains only b's
    Similar — breaks balance.
  Case 3: vxy contains only c's
    Similar.
  Case 4: vxy contains a's and b's
    Pumping changes a and b counts but not c.
    uv²xy²z has unequal counts. ∉ L.
  Case 5: vxy contains b's and c's
    Similar.

In all cases, we get a string not in L.
Contradiction. Therefore L is NOT context-free. ∎
""")

# EXAMPLE 3: ww — NOT CFL
print("=== Example: L = { ww | w ∈ {a,b}* } ===")
print("""
This is NOT context-free!

PROOF:
Assume L is a CFL with pumping length p.
Choose w = aᵖbᵖaᵖbᵖ ∈ L. (w = aᵖbᵖ, so ww = aᵖbᵖaᵖbᵖ)

By pumping lemma: w = uvxyz with |vxy| ≤ p, |vy| ≥ 1.

Since |vxy| ≤ p, vxy is within a window of p chars.
The string has blocks: aᵖ, bᵖ, aᵖ, bᵖ.
A window of length p can span at most 2 blocks.

Case analysis:
  - vxy in first a-block: pumping changes first a count.
    uv²xy²z has more a's in first block. ∉ L.
  - vxy spans a-b boundary: pumping affects counts.
    Breaks the ww structure.
  - vxy in first b-block: similar.
  - etc.

All cases fail. Contradiction. L is NOT context-free. ∎
""")

# EXAMPLE 4: a^i b^j c^k, i < j < k — NOT CFL
print("=== Example: L = { aⁱbʲcᵏ | i < j < k } ===")
print("""
This is NOT context-free.

PROOF:
Assume CFL with pumping length p.
Choose w = aᵖbᵖ⁺¹cᵖ⁺² ∈ L.

By pumping: w = uvxyz, |vxy| ≤ p, |vy| ≥ 1.

Since |vxy| ≤ p, vxy spans at most 2 of the 3 blocks.

Case 1: vxy in a-block only.
  Pumping increases a's. But then i grows.
  uv²xy²z has i+... a's, still i < j? Depends.
  Actually, if v = a^m, y = ε:
    uv²xy²z has p+m a's, p+1 b's, p+2 c's.
    Need p+m < p+1 → m < 1 → m = 0. Contradiction!
  So uv²xy²z violates i < j. ∉ L.

Case 2: vxy in b-block only.
  Similar — pumping b's.
  uv²xy²z has p a's, p+1+m b's, p+2 c's.
  Need p+1+m < p+2 → m < 1. Contradiction!

Case 3: vxy in c-block only.
  Pumping c's: uv²xy²z has more c's. Still j < k?
  Actually j = p+1, k = p+2+m. j < k holds.
  But wait — we need i < j < k.
  i = p, j = p+1, k = p+2+m.
  p < p+1 < p+2+m ✓ for all m ≥ 0.
  Hmm, this case doesn't break!
  
  We need a better string. Use w = aᵖbᵖcᵖ⁺¹?
  Then k = p+1. Pumping c's:
  uv²xy²z: k = p+1+m. Need j < k.
  j = p. p < p+1+m ✓ for m ≥ 0.
  Still works!
  
  Let's try w = aᵖbᵖ⁺¹cᵖ⁺² again.
  Case 3: vxy in c-block.
  v = c^m, y = ε (or v=ε, y=c^m).
  uv²xy²z has p a's, p+1 b's, p+2+m c's.
  i < j < k: p < p+1 < p+2+m ✓.
  So this pumped string IS in L!
  ✗ Case 3 fails to give contradiction.

We need a different approach.
Use w = aᵖbᵖcᵖ⁺¹? No, need i



  
  
    🎯 CFL Examples
    🎯 More Non-CFL Proofs
These languages are not context-free. Their proofs use the CFL pumping lemma with careful case analysis.
     Classic Non-CFL Languages
aⁿbⁿcⁿ: Three-way counting. ww: Copying. aⁱb^jc^k, i<j<k: Two inequalities. a^n²: Quadratic. Primes: Number theory.
🔢 Triple counting📋 Copying📊 Inequalities🔢 Squares
    # CFL Pumping Lemma — Classic Examples
print("=" * 60)
print("CLASSIC NON-CFL LANGUAGES")
print("=" * 60)

# 1. a^n b^n c^n
print("""
=== 1. L₁ = { aⁿbⁿcⁿ | n ≥ 0 } ===

PROOF:
  Assume L₁ is CFL with pumping length p.
  Choose w = aᵖbᵖcᵖ ∈ L₁.
  By pumping lemma: w = uvxyz, |vxy| ≤ p, |vy| ≥ 1.

  Since |vxy| ≤ p, vxy spans at most 2 of the 3 blocks
  (a-block, b-block, c-block). It CANNOT contain all three.

  Case 1: vxy contains only a's (possibly with v or y empty).
    Then pumping changes only the count of a's.
    uv²xy²z has more a's than b's or c's.
    Since a count ≠ b count or c count → ∉ L₁.
    
  Case 2: vxy contains only b's.
    Similar — changes b count only.
    uv²xy²z has unequal counts. ∉ L₁.
    
  Case 3: vxy contains only c's.
    Similar. ∉ L₁.
    
  Case 4: vxy contains a's and b's.
    Pumping changes a and b counts but not c.
    uv²xy²z has c count unchanged, but a/b counts change.
    For equality: a=b=c needed. But c is fixed, a/b change.
    So at most one of a or b can equal c. ∉ L₁.
    
  Case 5: vxy contains b's and c's.
    Similar. ∉ L₁.

  In all cases, uv²xy²z ∉ L₁.
  Contradiction. Therefore L₁ is NOT context-free. ∎
""")

# 2. ww
print("""
=== 2. L₂ = { ww | w ∈ {a,b}* } ===

PROOF:
  Assume L₂ is CFL with pumping length p.
  Choose w = aᵖbᵖaᵖbᵖ ∈ L₂. (w = aᵖbᵖ, ww = aᵖbᵖaᵖbᵖ)
  By pumping: w = uvxyz, |vxy| ≤ p, |vy| ≥ 1.

  The string has 4 blocks: aᵖ, bᵖ, aᵖ, bᵖ.
  |vxy| ≤ p means vxy spans at most 2 adjacent blocks.

  Case 1: vxy entirely within first a-block.
    Pumping increases first a's.
    uv²xy²z = aᵖ⁺ᵐbᵖaᵖbᵖ.
    First half: aᵖ⁺ᵐbᵖ... but second half: ...aᵖbᵖ.
    Not of form ww. ∉ L₂.
    
  Case 2: vxy spans first a-block and first b-block.
    Pumping changes counts in a way that breaks ww.
    ∉ L₂.
    
  Case 3: vxy within first b-block.
    Similar. ∉ L₂.
    
  Case 4: vxy spans first b-block and second a-block.
    Similar. ∉ L₂.
    
  Case 5: vxy within second a-block.
    Similar. ∉ L₂.
    
  Case 6: vxy within second b-block.
    Similar. ∉ L₂.
    
  (And all intermediate positions — same idea.)

  In all cases, contradiction.
  Therefore L₂ is NOT context-free. ∎
""")

# 3. a^i b^j c^k, i < j < k
print("""
=== 3. L₃ = { aⁱbʲcᵏ | i < j < k } ===

PROOF:
  Assume L₃ is CFL with pumping length p.
  Choose w = aᵖbᵖ⁺¹cᵖ⁺² ∈ L₃. (p < p+1 < p+2 ✓)
  By pumping: w = uvxyz, |vxy| ≤ p, |vy| ≥ 1.

  vxy spans at most 2 blocks.

  Case 1: vxy in a-block only.
    v = a^m, y = ε (or v=ε, y=a^m), m ≥ 1.
    uv²xy²z = aᵖ⁺ᵐbᵖ⁺¹cᵖ⁺².
    Need i < j: p+m < p+1 → m < 1. But m ≥ 1. ✗
    ∉ L₃.
    
  Case 2: vxy in b-block only.
    v = b^m, y = ε (or similar).
    uv²xy²z = aᵖbᵖ⁺¹⁺ᵐcᵖ⁺².
    Need j < k: p+1+m < p+2 → m < 1. ✗
    ∉ L₃.
    
  Case 3: vxy in c-block only.
    v = c^m, y = ε (or similar).
    uv²xy²z = aᵖbᵖ⁺¹cᵖ⁺²⁺ᵐ.
    i < j < k: p < p+1 < p+2+m ✓ for all m ≥ 0.
    ⚠️ This doesn't break! Need k=0:
    uv⁰xy⁰z = aᵖbᵖ⁺¹cᵖ⁺²⁻ᵐ (if v=c^m).
    Need j < k: p+1 < p+2-m → m < 1. ✗ if m ≥ 1.
    So with k=0: ∉ L₃. ✓
    
  Case 4: vxy spans a-block and b-block.
    v = a^m, y = b^n (or v=ε, y=a^m b^n, etc.)
    uv²xy²z = aᵖ⁺ᵐbᵖ⁺¹⁺ⁿcᵖ⁺².
    Need i < j: p+m < p+1+n → m < 1+n.
    Since m,n ≥ 0 and m+n ≥ 1, this can hold.
    Hmm, might be in L₃!
    
    Try k=0: uv⁰xy⁰z = aᵖ⁻ᵐbᵖ⁺¹⁻ⁿcᵖ⁺².
    Need i < j < k: p-m < p+1-n < p+2.
    Second: p+1-n < p+2 → -n < 1 → n > -1 ✓ always.
    First: p-m < p+1-n → -m < 1-n → n < m+1.
    If n ≤ m, holds. If n = m+1, fails.
    
    This case is tricky! May need a different string.
    
  Better: Use w = aᵖbᵖ⁺¹cᵖ⁺² and consider all cases.
  Or use closure properties with a simpler known non-CFL.
  
  Actually, the standard proof uses w = aᵖbᵖcᵖ⁺¹
  and more careful analysis. Or uses intersection:
  
  L₃ ∩ a*b*c* = { aⁱbʲcᵏ | i < j < k }
  If L₃ were CFL, intersection would be CFL.
  But aⁱbʲcᵏ (i p² + p.)
  
  So p² + m is strictly between p² and (p+1)².
  Not a perfect square.
  
  uv²xy²z ∉ L₄.
  Contradiction. L₄ is NOT context-free. ∎
""")

# 5. Primes (as CFL)
print("""
=== 5. L₅ = { aᵖ | p is prime } ===

PROOF:
  Assume L₅ is CFL with pumping length p.
  Choose w = a^q where q is prime and q ≥ p.
  By pumping: w = uvxyz, |vxy| ≤ p, |vy| ≥ 1.
  
  Let |vy| = m, 1 ≤ m ≤ p.
  
  Consider uv^(q+1)xy^(q+1)z:
    Length = q + q·m = q(m+1).
    This is composite (divisible by q and m+1).
    ∉ L₅ (not prime).
  
  Contradiction. L₅ is NOT context-free. ∎
""")

# 6. More examples
print("""
=== 6. L₆ = { aⁱbⁱcⁱ | i ≥ 0 } ===
  Same as aⁿbⁿcⁿ. NOT CFL.

=== 7. L₇ = { aⁱbⁱcⁱdⁱ | i ≥ 0 } ===
  Also NOT CFL. Even more counters.

=== 8. L₈ = { w | w has equal a's, b's, c's } ===
  NOT CFL. Requires 3-way counting.

=== 9. L₉ = { aⁱbⁱ | i is prime } ===
  NOT CFL. Combines counting and number theory.

=== 10. L₁₀ = { aⁱbⁱcⁱ | i is not prime } ===
  NOT CFL. (Complement of non-CFL within a*b*c*
  is not necessarily non-CFL, but this one is.)
""")

# SUMMARY TABLE
print("=== Summary Table ===")
print(f"{'Language':<30} {'Regular?':<12} {'CFL?':<12} {'Pumping String':<20}")
print("-" * 74)
print(f"{'aⁿbⁿ':<30} {'No':<12} {'Yes':<12} {'aᵖbᵖ':<20}")
print(f"{'aⁿbⁿcⁿ':<30} {'No':<12} {'No':<12} {'aᵖbᵖcᵖ':<20}")
print(f"{'ww':<30} {'No':<12} {'No':<12} {'aᵖbᵖaᵖbᵖ':<20}")
print(f"{'w = wᴿ':<30} {'No':<12} {'Yes':<12} {'aᵖbaᵖ':<20}")
print(f"{'aⁿ²':<30} {'No':<12} {'No':<12} {'aᵖ²':<20}")
print(f"{'aⁿ (prime)':<30} {'No':<12} {'No':<12} {'a^q prime':<20}")
print(f"{'aⁱbʲ, i

  


  
  
    🔬 Ogden's Lemma
    🎯 A Stronger Pumping Lemma
Ogden's Lemma is a generalization of the pumping lemma. It lets you mark specific positions in the string, and guarantees the pumped part includes at least one marked position. This makes proofs easier for certain languages.
     Ogden's Lemma Statement
If L is CFL: ∃ pumping length p. ∀ w ∈ L: |w| ≥ p. Mark ≥ p positions: Choose p positions to mark. ∃ decomposition: w = uvxyz. |vxy| ≤ p: At most p chars. vy has ≥ 1 marked: At least one marked in v or y. ∀ k ≥ 0: uv^kxy^kz ∈ L.
📍 Marked positions|vxy| ≤ pvy hits markedStronger
    # Ogden's Lemma
print("""
=== Ogden's Lemma — Formal Statement ===

If L is a context-free language, then:
  ∃ p ≥ 1 (pumping length)
  ∀ w ∈ L with |w| ≥ p
    For ANY choice of ≥ p marked positions in w:
      ∃ decomposition w = uvxyz such that:
        1. |vxy| ≤ p
        2. v and y together contain ≥ 1 marked position
        3. ∀ k ≥ 0: uv^k xy^k z ∈ L

=== Comparison with CFL Pumping Lemma ===

CFL Pumping:  w = uvxyz, |vxy| ≤ p, |vy| ≥ 1
Ogden's:      w = uvxyz, |vxy| ≤ p, vy contains ≥ 1 marked position

Ogden's is STRONGER:
  - You get to choose which positions are "important"
  - The pumped part must include an important position
  - Makes some proofs easier

=== Why It's Stronger ===

The regular pumping lemma can fail for some
non-regular languages (they satisfy it).

Ogden's lemma is harder to satisfy.
More languages fail Ogden's than fail the
regular pumping lemma.

Still not sufficient (some non-CFLs satisfy Ogden's),
but closer to a characterization.
""")

# EXAMPLE: a^n b^n c^n (easier with Ogden)
print("=== Example: aⁿbⁿcⁿ with Ogden's Lemma ===")
print("""
L = { aⁿbⁿcⁿ | n ≥ 0 } is NOT context-free.

PROOF (using Ogden's Lemma):
  Assume L is CFL with pumping length p.
  Choose w = aᵖbᵖcᵖ ∈ L.
  Mark ALL p a's. (There are exactly p a's.)
  
  By Ogden's lemma: w = uvxyz with:
    - |vxy| ≤ p
    - vy contains ≥ 1 marked position (i.e., ≥ 1 a)
    - ∀k: uv^k xy^k z ∈ L
  
  Since vy contains ≥ 1 a, and |vxy| ≤ p,
  vxy cannot extend past the b-block
  (because that would require > p chars).
  
  Actually, vxy could be within a-block or span a-b boundary.
  But it can't reach c-block (too far).
  
  Case 1: vxy entirely in a-block.
    Pumping changes a count only.
    uv²xy²z has more a's than b's. ∉ L.
    
  Case 2: vxy spans a-block and b-block.
    v and y could be a's and b's.
    Pumping changes a and b counts.
    Since c count is fixed, and a=b=c required,
    uv²xy²z can't have all equal. ∉ L.
    
  Case 3: vxy in b-block only — impossible,
    because vy must contain a marked position (an a).
    So vy contains ≥ 1 a, meaning vxy includes an a.
    
  In all valid cases, contradiction.
  Therefore L is NOT context-free. ∎

Note: Ogden's lemma made this proof cleaner
because we forced the pumped part to include an a.
""")

# EXAMPLE: ww (easier with Ogden)
print("=== Example: ww with Ogden's Lemma ===")
print("""
L = { ww | w ∈ {a,b}* } is NOT context-free.

PROOF (using Ogden's Lemma):
  Assume L is CFL with pumping length p.
  Choose w = aᵖbᵖaᵖbᵖ ∈ L.
  Mark the middle bᵖaᵖ boundary region...
  
  Actually, mark the first b-block (p b's).
  Wait — need ≥ p marks. First b-block has p b's. ✓
  
  By Ogden's: w = uvxyz, |vxy| ≤ p,
  vy contains ≥ 1 marked b.
  
  Since |vxy| ≤ p and contains a b from first b-block,
  vxy is within first b-block or spans a-b boundary.
  
  Case 1: vxy in first b-block.
    Pumping changes first b count.
    uv²xy²z has different first and second b counts.
    Can't be ww (halves must be equal). ∉ L.
    
  Case 2: vxy spans first a-block and first b-block.
    vy contains both a's and b's.
    Pumping changes both counts in first half.
    Second half unchanged. Not ww. ∉ L.
    
  Case 3: vxy spans first b-block and second a-block.
    Similar. ∉ L.
    
  Contradiction. L is NOT context-free. ∎
""")

# EXAMPLE: a^i b^j c^k, i

  


  
  
    🔒 Closure Properties
    🎯 Using Closure to Prove Non-Regularity/Non-CFL
Closure properties provide an alternative to pumping lemma proofs. If L is regular, then L ∩ R (R regular) is regular. So if L ∩ R is non-regular, L must be non-regular.
     Closure Properties
Regular closed under: Union, intersection, complement, concat, star. CFL closed under: Union, concat, star, ∩ regular. CFL NOT closed under: Intersection, complement. Trick: L ∩ R = non-regular ⟹ L non-regular. Trick: L ∩ R = non-CFL ⟹ L non-CFL.
🔒 Closure∩ RegularComplementShortcut
    # Closure Properties for Non-Regularity Proofs
print("=" * 60)
print("CLOSURE PROPERTIES")
print("=" * 60)

# 1. REGULAR LANGUAGE CLOSURE
print("""
=== Regular Languages Are Closed Under ===

✓ Union:           L1 ∪ L2
✓ Intersection:    L1 ∩ L2
✓ Complement:      Σ* \ L
✓ Difference:      L1 \ L2
✓ Concatenation:   L1 · L2
✓ Kleene Star:     L*
✓ Reversal:        L^R
✓ Homomorphism:    h(L)

=== Key Property for Proofs ===

If L is regular and R is regular,
then L ∩ R is regular.

Contrapositive:
If L ∩ R is NOT regular (for some regular R),
then L is NOT regular.
""")

# 2. EXAMPLE: { a^i b^j | i = j or i ≠ j }
print("""
=== Example: L = { aⁱbʲ | i = j or i ≠ j } ===

This is just a*b*! Which IS regular.
Not a good example.

Better: L = { aⁱbʲ | i = j } is not regular.
We know this from pumping lemma.

Alternative proof using closure:
  Assume L = { aⁱbʲ | i = j } is regular.
  Then L ∩ a*b* = L is regular (trivially).
  Not helpful.
  
  Try: L' = { aⁱbʲ | i ≠ j }.
  L' = a*b* \ L.
  If L were regular, L' would be regular (closure under difference).
  But L' is not regular (can prove by pumping).
  Contradiction. L is not regular.
""")

# 3. CLASSIC TRICK: INTERSECTION WITH REGULAR
print("""
=== Classic Trick: Intersection with Regular ===

To prove L is not regular:
  1. Find a regular language R
  2. Show L ∩ R is not regular
  3. Conclude L is not regular

Why it works:
  If L were regular, L ∩ R would be regular.
  But L ∩ R is not regular. Contradiction.

Example: L = { w | w has equal a's and b's }
  L ∩ a*b* = { aⁱbʲ | i = j } = aⁿbⁿ
  aⁿbⁿ is not regular.
  Therefore L is not regular.
""")

# 4. EXAMPLE: EQUAL A'S AND B'S
print("""
=== Example: L = { w | #a(w) = #b(w) } ===

PROOF:
  Assume L is regular.
  Let R = a*b* (regular).
  Then L ∩ R = { aⁱbʲ | i = j } = { aⁿbⁿ }.
  
  { aⁿbⁿ } is not regular (proved by pumping).
  But L ∩ R should be regular (closure).
  Contradiction.
  
  Therefore L is NOT regular. ∎
""")

# 5. EXAMPLE: ww
print("""
=== Example: L = { ww | w ∈ {a,b}* } ===

PROOF:
  Assume L is regular.
  Let R = a*b*a*b* (regular).
  Then L ∩ R = { aⁱbʲaᵏbˡ | i=k, j=l }.
  
  Is this regular? No! (Can prove by pumping.)
  Actually, { aⁱbʲaⁱbʲ } = { ww | w = aⁱbʲ }.
  This is not regular.
  
  Contradiction. L is not regular. ∎
""")

# 6. CFL CLOSURE
print("""
=== CFL Closure Properties ===

CFLs are closed under:
  ✓ Union
  ✓ Concatenation
  ✓ Kleene Star
  ✓ Intersection with regular languages
  ✓ Homomorphism
  ✓ Reversal

CFLs are NOT closed under:
  ✗ Intersection (two CFLs)
  ✗ Complement
  ✗ Difference

Key trick for non-CFL:
  If L ∩ R is not CFL (R regular),
  then L is not CFL.
""")

# 7. EXAMPLE: a^n b^n c^n
print("""
=== Example: L = { aⁿbⁿcⁿ } ===

We know it's not CFL (pumping lemma).

Alternative proof using closure:
  Assume L is CFL.
  L ∩ a*b*c* = L (trivially).
  Not helpful.
  
  Try: L' = { aⁱbⁱcⁱ | i ≥ 0 } = L.
  We need a different approach.
  
  Consider L1 = { aⁱbⁱcʲ | i,j ≥ 0 } (CFL)
  L2 = { aⁱbʲcʲ | i,j ≥ 0 } (CFL)
  L1 ∩ L2 = { aⁱbⁱcⁱ } = L.
  
  If CFLs were closed under intersection,
  L would be CFL. But it's not.
  (This shows CFLs are NOT closed under intersection!)
""")

# 8. EXAMPLE: { a^i b^j c^k | i < j < k }
print("""
=== Example: L = { aⁱbʲcᵏ | i < j < k } ===

PROOF using closure:
  Assume L is CFL.
  Let R = a*b*c* (regular).
  Then L ∩ R = L (trivially).
  Not helpful directly.
  
  Use: L ∩ aⁱbⁱc* = { aⁱbⁱcᵏ | i < k }.
  Is this CFL? Hmm.
  
  Better: Use L1 = { aⁱbⁱcʲ | i,j ≥ 0 }
         L2 = { aⁱbʲcʲ | i,j ≥ 0 }
  L1 ∩ L2 = { aⁱbⁱcⁱ } = not CFL.
  
  But this shows CFLs not closed under ∩,
  not directly that L is not CFL.
  
  For L itself: use Ogden's lemma or
  show L ∩ a*b*c* = L and use known result.
""")

# 9. GENERAL STRATEGY
print("""
=== General Strategy ===

To prove L is NOT regular:
  1. Try pumping lemma directly
  2. If tricky, find R regular such that L ∩ R is non-regular
  3. Conclude L is non-regular

To prove L is NOT context-free:
  1. Try CFL pumping lemma or Ogden's lemma
  2. If tricky, use closure:
     - L1 ∩ L2 = L where L1, L2 are CFL
     - If L is non-CFL, this shows CFLs not closed under ∩
     - Or find R regular with L ∩ R non-CFL

Common regular languages to intersect with:
  - a*b*     (forces a's then b's)
  - a*b*c*   (forces 3 blocks)
  - (ab)*    (forces alternating)
  - a*       (only a's)
""")

# 10. SUMMARY TABLE
print("=== Closure Summary ===")
print(f"{'Operation':<25} {'Regular':<15} {'CFL':<15}")
print("-" * 55)
print(f"{'Union':<25} {'✓ Closed':<15} {'✓ Closed':<15}")
print(f"{'Intersection':<25} {'✓ Closed':<15} {'✗ Not closed':<15}")
print(f"{'Complement':<25} {'✓ Closed':<15} {'✗ Not closed':<15}")
print(f"{'Difference':<25} {'✓ Closed':<15} {'✗ Not closed':<15}")
print(f"{'Concatenation':<25} {'✓ Closed':<15} {'✓ Closed':<15}")
print(f"{'Kleene Star':<25} {'✓ Closed':<15} {'✓ Closed':<15}")
print(f"{'Reversal':<25} {'✓ Closed':<15} {'✓ Closed':<15}")
print(f"{'∩ Regular':<25} {'✓ Closed':<15} {'✓ Closed':<15}")
print(f"{'Homomorphism':<25} {'✓ Closed':<15} {'✓ Closed':<15}")
print(f"{'Inverse Homomorphism':<25} {'✓ Closed':<15} {'✓ Closed':<15}")

print("""
Key insight:
  Regular languages are closed under almost everything.
  CFLs are NOT closed under intersection/complement.
  This is why aⁿbⁿcⁿ is not CFL:
    { aⁱbⁱcʲ } ∩ { aⁱbʲcʲ } = { aⁿbⁿcⁿ }
    Both are CFLs, but intersection is not.
    So CFLs are not closed under intersection.
""")
  

  
  
    📊 Myhill-Nerode
    🎯 A Complete Characterization
The Myhill-Nerode theorem gives a necessary and sufficient condition for a language to be regular. It's stronger than the pumping lemma — it can prove both regularity AND non-regularity.
     Myhill-Nerode Theorem
Equivalence relation: x ~_L y iff for all z: xz ∈ L ↔ yz ∈ L. Distinguishable: x and y are distinguishable if ∃z: xz ∈ L but yz ∉ L. Theorem: L is regular iff ~_L has finitely many equivalence classes. Number of classes: Equals minimal DFA states. Sufficient: Proves both directions. Stronger: Than pumping lemma.
~_L EquivalenceDistinguishableFinite classesMinimal DFA
    # Myhill-Nerode Theorem
print("""
=== Myhill-Nerode Theorem ===

Define equivalence relation ~_L on strings:
  x ~_L y  iff  for all z ∈ Σ*: (xz ∈ L) ⟺ (yz ∈ L)

Two strings are equivalent if they have the same
"future behavior" — no suffix can tell them apart.

Theorem: L is regular
         ⟺
         ~_L has finitely many equivalence classes.

Moreover, the number of equivalence classes
equals the number of states in the minimal DFA for L.

=== Distinguishability ===

x and y are distinguishable (x ≁_L y) if:
  ∃ z ∈ Σ*: xz ∈ L but yz ∉ L

z is called a "distinguishing string" for x and y.

=== How to Use ===

To prove L is NOT regular:
  Show there are infinitely many equivalence classes.
  I.e., find infinitely many strings that are
  pairwise distinguishable.

To prove L IS regular:
  Show there are finitely many equivalence classes.
  (Usually by constructing a DFA.)
""")

# EXAMPLE: a^n b^n
print("=== Example: L = { aⁿbⁿ | n ≥ 0 } ===")
print("""
PROOF (non-regular using Myhill-Nerode):

Consider the strings: a¹, a², a³, a⁴, ...
(We'll show they're pairwise distinguishable.)

For i ≠ j, consider x = aⁱ, y = aʲ.
Choose z = bⁱ.
  xz = aⁱbⁱ ∈ L ✓
  yz = aʲbⁱ ∉ L (since j ≠ i)
  
So z distinguishes x and y.
Therefore aⁱ ≁_L aʲ for all i ≠ j.

There are INFINITELY many equivalence classes:
  [ε], [a], [aa], [aaa], ...

By Myhill-Nerode, L is NOT regular. ∎

This is often CLEANER than pumping lemma!
""")

# EXAMPLE: EVEN LENGTH
print("=== Example: L = { w | |w| is even } ===")
print("""
This IS regular.

Equivalence classes:
  [ε] = { w | |w| even }     — even length
  [a] = { w | |w| odd }      — odd length

Only 2 classes!
By Myhill-Nerode, L is regular.
Minimal DFA has 2 states. ✓

Check:
  x = ε, y = aa: both even length.
    For all z: xz even ⟺ yz even ✓
  x = ε, y = a: even vs odd.
    z = ε: xz = ε ∈ L, yz = a ∉ L ✓ distinguishable
""")

# EXAMPLE: EQUAL A'S AND B'S
print("=== Example: L = { w | #a(w) = #b(w) } ===")
print("""
PROOF (non-regular):

Consider strings: a⁰, a¹, a², ...
For i ≠ j, x = aⁱ, y = aʲ.
Choose z = bⁱ.
  xz = aⁱbⁱ has equal a's and b's ✓
  yz = aʲbⁱ has unequal (j ≠ i) ✗
  
Distinguishable! Infinitely many classes.
Therefore L is NOT regular. ∎
""")

# EXAMPLE: PALINDROMES
print("=== Example: L = { w | w = wᴿ } ===")
print("""
PROOF (non-regular):

Consider strings: a⁰, a¹, a², ...
For i ≠ j, x = aⁱ, y = aʲ.
Choose z = baⁱ.
  xz = aⁱbaⁱ is a palindrome ✓
  yz = aʲbaⁱ is not (unless i = j) ✗
  
Distinguishable! Infinitely many classes.
L is NOT regular. ∎
""")

# MYHILL-NERODE VS PUMPING LEMMA
print("=== Myhill-Nerode vs Pumping Lemma ===")
print(f"{'Aspect':<30} {'Pumping Lemma':<25} {'Myhill-Nerode':<25}")
print("-" * 80)
print(f"{'Direction':<30} {'Necessary only':<25} {'Necessary & sufficient':<25}")
print(f"{'Can prove regular?':<30} {'No':<25} {'Yes':<25}")
print(f"{'Can prove non-regular?':<30} {'Yes':<25} {'Yes':<25}")
print(f"{'Proof style':<30} {'Contradiction':<25} {'Counting classes':<25}")
print(f"{'Difficulty':<30} {'Often easier':<25} {'More abstract':<25}")
print(f"{'Exact state count':<30} {'No':<25} {'Yes (minimal DFA)':<25}")
print(f"{'Works for all?':<30} {'No (necessary only)':<25} {'Yes (characterization)':<25}")

# ANOTHER EXAMPLE: FINITE LANGUAGE
print("=== Example: Finite Languages Are Regular ===")
print("""
Any finite language is regular.

L = { "cat", "dog", "bird" }

Equivalence classes:
  Each string in L and its prefixes form classes.
  Finitely many strings → finitely many classes.
  
  By Myhill-Nerode, L is regular. ✓
  
  Minimal DFA: a trie of the strings.
""")

# ANOTHER EXAMPLE: a*b*
print("=== Example: L = a*b* ===")
print("""
This IS regular.

Equivalence classes:
  [ε]      — strings of all a's (or empty)
  [a]      — strings of all a's
  [ab]     — strings of a's followed by b's
  [b]      — strings of all b's
  [ba]     — contains "ba" (dead state)

Actually let's think more carefully:

States of minimal DFA:
  q0: seen a's only (or nothing)
  q1: seen a's then b's
  q2: seen "ba" (dead — can't recover)

Classes:
  [ε]: strings in a*           — can still accept
  [ab]: strings in a*b+        — can still accept
  [ba]: strings containing "ba" — dead

3 equivalence classes.
Minimal DFA has 3 states. ✓
""")

# MYHILL-NERODE PROOF
print("=== Proof Sketch ===")
print("""
(⟹) If L is regular, then ~_L has finitely many classes.

Let M = (Q, Σ, δ, q0, F) be a DFA for L.
Define x ~_M y iff δ*(q0, x) = δ*(q0, y).
This is an equivalence relation with ≤ |Q| classes.

Claim: x ~_M y ⟹ x ~_L y.
Proof: If δ*(q0, x) = δ*(q0, y), then for any z,
  δ*(q0, xz) = δ*(δ*(q0, x), z) = δ*(δ*(q0, y), z) = δ*(q0, yz).
  So xz ∈ L ⟺ δ*(q0, xz) ∈ F ⟺ δ*(q0, yz) ∈ F ⟺ yz ∈ L.
  Therefore x ~_L y.

So ~_L is coarser than ~_M, hence has ≤ |Q| classes. ∎

(⟸) If ~_L has finitely many classes, L is regular.

Construct DFA:
  States: equivalence classes of ~_L
  Start: [ε]
  Transitions: [x] --a--> [xa]
  Accept: [x] where x ∈ L

This is well-defined (if x ~_L y, then xa ~_L ya).
It accepts exactly L.
Therefore L is regular. ∎
""")

# HOW TO USE
print("=== How to Use Myhill-Nerode ===")
print("""
STEP 1: Identify the language L.

STEP 2: Try to find equivalence classes.
  - What "information" about a prefix matters?
  - When do two prefixes behave the same?

STEP 3: If finitely many classes → L is regular.
  - Construct minimal DFA from classes.

STEP 4: If infinitely many classes → L is not regular.
  - Exhibit infinitely many pairwise distinguishable strings.
  - Usually: a⁰, a¹, a², ... or similar.

STEP 5: Count classes → minimal DFA size.
""")

# COMMON DISTINGUISHING STRINGS
print("=== Common Distinguishing Strings ===")
print("""
For L = { aⁿbⁿ }:
  x = aⁱ, y = aʲ, z = bⁱ (or bʲ)

For L = { ww }:
  x = aⁱb, y = aʲb, z = aⁱb (or similar)

For L = { w = wᴿ }:
  x = aⁱ, y = aʲ, z = baⁱ

For L = { #a = #b }:
  x = aⁱ, y = aʲ, z = bⁱ

General rule:
  Choose z that "completes" x but not y.
  Often z = bⁱ where i is the count in x.
""")
  

  
  
    💼 Applications
    🎯 Real-World Uses of Pumping Lemma
The pumping lemma isn't just theory — it has practical applications in compiler design, regex engines, protocol verification, and understanding computational limits.
     Practical Applications
Regex limits: Know what regex can't do. Compiler design: When to use parser vs lexer. Protocol verification: Finite state limits. Security: Input validation limits. Education: Understanding computation. Research: Language classification.
🔤 Regex limits💻 Compilers🌐 Protocols🔒 Security
    # Applications of the Pumping Lemma
print("=" * 60)
print("PRACTICAL APPLICATIONS")
print("=" * 60)

# 1. REGEX LIMITATIONS
print("""
=== 1. Regex Limitations ===

The pumping lemma tells us what regex CANNOT do:

✗ Balanced parentheses: aⁿbⁿ
✗ Matching tags: ... (nested)
✗ Palindromes: w = wᴿ
✗ Equal counts: #a = #b
✗ Prime length strings

Why it matters:
  - Don't try to parse HTML with regex
  - Don't validate nested structures with regex
  - Use proper parsers for these

Example: JSON validation
  ✗ Regex can't validate nested JSON
  ✓ Use a JSON parser

Example: Email validation
  ✓ Regex is fine (regular pattern)
  ✗ Nested comments can't be done
""")

# 2. COMPILER DESIGN
print("""
=== 2. Compiler Design ===

Lexical analysis (tokenization):
  - Regular languages (DFA/NFA)
  - Identifiers, numbers, keywords, operators

Parsing (syntax analysis):
  - Context-free languages (CFG/PDA)
  - Expressions, statements, nested blocks

The pumping lemma helps decide:
  - What can be done with regex (lexer)
  - What needs a parser (CFG)

Example: Balanced parentheses in code
  if (x > 0) { if (y > 0) { ... } }
  This requires a parser — not regex!

Example: Arithmetic expressions
  1 + 2 * (3 - 4) / 5
  Also needs a parser — nesting!
""")

# 3. PROTOCOL VERIFICATION
print("""
=== 3. Protocol Verification ===

Network protocols are often modeled as state machines.

The pumping lemma tells us:
  - What protocols can be verified with FSMs
  - What requires more powerful models

Example: TCP sequence numbers
  - Need to track sequence numbers (unbounded)
  - Not regular — need more than FSM

Example: HTTP request/response
  - Mostly regular (headers, methods)
  - But nested structures (JSON body) need parser

Example: TLS handshake
  - State machine (regular)
  - But crypto operations need more
""")

# 4. SECURITY
print("""
=== 4. Security ===

Input validation:
  - Regex is great for simple patterns
  - But can't validate nested structures

Example: SQL injection prevention
  - Regex can filter simple patterns
  - But SQL is context-free
  - Use parameterized queries instead

Example: XSS prevention
  - Regex can filter simple cases
  - But HTML is context-free
  - Use proper HTML sanitizers

Example: Path traversal
  - Regex can check for "../"
  - But filesystem paths are complex
  - Use canonicalization

Lesson: Know the limits of regex!
""")

# 5. EDUCATION
print("""
=== 5. Education ===

The pumping lemma teaches:

1. LIMITS OF COMPUTATION
   - Finite memory has limits
   - Some problems need more power

2. PROOF TECHNIQUES
   - Contradiction
   - Case analysis
   - Pigeonhole principle

3. ABSTRACTION
   - From machines to languages
   - From languages to classes

4. CLASSIFICATION
   - Regular vs Context-Free vs ...
   - Chomsky hierarchy

5. PRACTICAL JUDGMENT
   - When to use regex
   - When to use parser
   - When to use something else
""")

# 6. LANGUAGE CLASSIFICATION
print("""
=== 6. Language Classification ===

The pumping lemma helps classify languages:

REGULAR LANGUAGES:
  - Recognized by DFA/NFA
  - Described by regex
  - Pumping lemma (regular version)

CONTEXT-FREE LANGUAGES:
  - Recognized by PDA
  - Described by CFG
  - Pumping lemma (CFL version)
  - Ogden's lemma

CONTEXT-SENSITIVE:
  - Recognized by LBA
  - More powerful

RECURSIVELY ENUMERABLE:
  - Recognized by Turing machines
  - Most powerful

Chomsky hierarchy:
  Type 3 (Regular) ⊂ Type 2 (CFL) ⊂ Type 1 (CS) ⊂ Type 0 (RE)
""")

# 7. DECISION PROCEDURES
print("""
=== 7. Decision Procedures ===

The pumping lemma helps decide:

FOR REGULAR LANGUAGES:
  - Membership: O(n)
  - Emptiness: decidable
  - Equivalence: decidable
  - Universality: decidable

FOR CFLs:
  - Membership: O(n³) (CYK algorithm)
  - Emptiness: decidable
  - Equivalence: UNDECIDABLE
  - Universality: UNDECIDABLE

FOR CSLs:
  - Membership: decidable
  - Emptiness: UNDECIDABLE

FOR RE:
  - Membership: UNDECIDABLE (halting problem)
""")

# 8. REAL-WORLD EXAMPLES
print("""
=== 8. Real-World Examples ===

1. HTML PARSING
   - HTML is context-free (nested tags)
   - Regex can't parse HTML properly
   - Use an HTML parser

2. JSON VALIDATION
   - JSON is context-free (nested objects/arrays)
   - Regex can't validate JSON
   - Use a JSON parser

3. PROGRAMMING LANGUAGES
   - Most languages are context-free
   - Some features (semantic analysis) need more
   - Regex only for lexical analysis

4. PROTEIN SEQUENCES
   - Some patterns are regular
   - Some need context-free
   - Some need more (folding)

5. NETWORK PROTOCOLS
   - Many are finite-state
   - Some need counters (TCP)
   - Some need full Turing machines
""")

# 9. SUMMARY TABLE
print("=== Application Summary ===")
print(f"{'Domain':<25} {'Use Case':<30} {'Pumping Role':<25}")
print("-" * 80)
print(f"{'Regex':<25} {'Validation':<30} {'Know limits':<25}")
print(f"{'Compilers':<25} {'Lexer vs parser':<30} {'Language class':<25}")
print(f"{'Security':<25} {'Input validation':<30} {'Structure limits':<25}")
print(f"{'Protocols':<25} {'State machines':<30} {'FSM limits':<25}")
print(f"{'Education':<25} {'Theory':<30} {'Proof technique':<25}")
print(f"{'Research':<25} {'Classification':<30} {'Chomsky hierarchy':<25}")

# 10. PRACTICAL TAKEAWAYS
print("""
=== Practical Takeaways ===

1. KNOW YOUR TOOLS
   - Regex = regular languages
   - Parsers = context-free
   - Turing machines = everything

2. MATCH TOOL TO PROBLEM
   - Simple patterns → regex
   - Nested structures → parser
   - General computation → programming

3. UNDERSTAND LIMITS
   - Regex can't count (beyond finite)
   - Regex can't match nested structures
   - Regex can't handle backreferences (in DFA form)

4. USE THE RIGHT ABSTRACTION
   - Don't force regex where it doesn't fit
   - Use parser generators for complex grammars
   - Use recursive descent for hand-written parsers

5. THE PUMPING LEMMA IS YOUR FRIEND
   - Proves when regex won't work
   - Guides tool selection
   - Prevents wasted effort
""")
  

  
  
    🚀 Limits & Beyond
    🎯 The Bigger Picture
The pumping lemma is part of the Chomsky hierarchy — a classification of formal languages by their computational power. Understanding these limits is fundamental to computer science.
     Beyond Regular & CFL
Chomsky hierarchy: Regular ⊂ CFL ⊂ CS ⊂ RE. Pumping lemma: Works for regular and CFL. Beyond: No simple pumping lemma. Decidability: Decreases as power increases. Applications: Compilers, verification, AI. Frontier: Quantum, biological computing.
📊 Chomsky🔬 Beyond CFL🧠 Decidability🚀 Frontiers
    # Limits and Beyond
print("=" * 60)
print("THE CHOMSKY HIERARCHY")
print("=" * 60)

print("""
=== Chomsky Hierarchy ===

Type 0: Recursively Enumerable (RE)
  - Recognized by: Turing machines
  - Grammar: unrestricted
  - Example: halting problem
  - Membership: undecidable

Type 1: Context-Sensitive (CS)
  - Recognized by: Linear bounded automata
  - Grammar: context-sensitive
  - Example: aⁿbⁿcⁿ
  - Membership: decidable (PSPACE)

Type 2: Context-Free (CFL)
  - Recognized by: Pushdown automata
  - Grammar: context-free
  - Example: aⁿbⁿ, palindromes
  - Membership: O(n³)

Type 3: Regular
  - Recognized by: Finite automata
  - Grammar: regular
  - Example: a*b*, (ab)*
  - Membership: O(n)

Inclusion: Regular ⊂ CFL ⊂ CS ⊂ RE
""")

# PUMPING LEMMA IN HIERARCHY
print("=== Pumping Lemma in the Hierarchy ===")
print("""
REGULAR:
  ✓ Pumping lemma (xyz)
  ✓ Myhill-Nerode
  ✓ Closure properties

CFL:
  ✓ Pumping lemma (uvxyz)
  ✓ Ogden's lemma
  ✓ Parikh's theorem
  ✓ Closure properties

CONTEXT-SENSITIVE:
  ✗ No simple pumping lemma
  ✓ Can use space complexity
  ✓ Decidable membership

RECURSIVELY ENUMERABLE:
  ✗ No pumping lemma
  ✗ Undecidable membership
  ✓ Turing machines
""")

# BEYOND CFL
print("=== Beyond Context-Free ===")
print("""
Languages that are NOT CFL:

1. aⁿbⁿcⁿ
   - Three-way counting
   - Context-sensitive

2. ww
   - Copying
   - Context-sensitive

3. aⁱbʲcᵏ, i < j < k
   - Two inequalities
   - Context-sensitive

4. { aⁿ | n is prime }
   - Number theory
   - Context-sensitive (maybe)

5. { aⁿ² | n ≥ 0 }
   - Quadratic
   - Context-sensitive

These require more than a stack (PDA).
They need a linear-bounded automaton (LBA).
""")

# DECIDABILITY
print("=== Decidability Landscape ===")
print(f"{'Problem':<30} {'Regular':<15} {'CFL':<15} {'CS':<15} {'RE':<15}")
print("-" * 90)
print(f"{'Membership':<30} {'✓ O(n)':<15} {'✓ O(n³)':<15} {'✓':<15} {'✗':<15}")
print(f"{'Emptiness':<30} {'✓':<15} {'✓':<15} {'✗':<15} {'✗':<15}")
print(f"{'Equivalence':<30} {'✓':<15} {'✗':<15} {'✗':<15} {'✗':<15}")
print(f"{'Universality':<30} {'✓':<15} {'✗':<15} {'✗':<15} {'✗':<15}")
print(f"{'Finiteness':<30} {'✓':<15} {'✓':<15} {'✗':<15} {'✗':<15}")
print(f"{'Intersection':<30} {'✓':<15} {'✗':<15} {'✓':<15} {'✓':<15}")
print(f"{'Complement':<30} {'✓':<15} {'✗':<15} {'✓':<15} {'✗':<15}")

# FRONTIERS
print("=== Frontiers ===")
print("""
1. QUANTUM AUTOMATA
   - Quantum finite automata
   - Superposition of states
   - Potentially more compact
   - Active research

2. PROBABILISTIC AUTOMATA
   - Random transitions
   - Accept with probability
   - Used in ML, NLP

3. BIO-INSPIRED COMPUTING
   - DNA computing
   - Membrane computing
   - Cellular automata

4. NEURAL AUTOMATA
   - Learned state machines
   - Differentiable automata
   - Integration with deep learning

5. PROGRAM SYNTHESIS
   - Generate programs from specs
   - Automata-based synthesis
   - Verified compilation

6. VERIFICATION
   - Model checking
   - Abstract interpretation
   - Automata-based verification
""")

# PUMPING LEMMA'S LEGACY
print("=== Pumping Lemma's Legacy ===")
print("""
The pumping lemma:

✓ FOUNDATIONAL
  - First tool for non-regularity
  - Basis for automata theory

✓ PEDAGOGICAL
  - Teaches proof techniques
  - Intuition about computation limits

✓ PRACTICAL
  - Guides tool selection
  - Prevents misuse of regex

✓ GENERALIZABLE
  - Ogden's lemma (stronger)
  - Parikh's theorem (counting)
  - Other pumping lemmas

✓ HISTORICAL
  - 1960s: Formal language theory
  - 1970s: Compiler construction
  - 1980s-90s: Verification
  - 2000s+: Modern applications

"All models are wrong, but some are useful."
  — George Box

The pumping lemma is a useful model
of computational limits.
""")

# FINAL THOUGHTS
print("=== Final Thoughts ===")
print("""
The pumping lemma teaches us:

1. FINITE MEMORY HAS LIMITS
   - Can't count arbitrarily high
   - Can't match nested structures
   - Can't remember long strings

2. PROOF TECHNIQUES
   - Contradiction
   - Pigeonhole principle
   - Case analysis

3. HIERARCHY OF COMPUTATION
   - Regular ⊂ CFL ⊂ CS ⊂ RE
   - Each level more powerful
   - Each level less decidable

4. PRACTICAL JUDGMENT
   - Know when regex works
   - Know when you need a parser
   - Know when you need more

5. BEAUTY OF THEORY
   - Simple proofs, deep insights
   - Elegant characterization
   - Foundation of CS

You now understand:
  ✓ Regular pumping lemma
  ✓ CFL pumping lemma
  ✓ Ogden's lemma
  ✓ Proof techniques
  ✓ Common mistakes
  ✓ Closure properties
  ✓ Myhill-Nerode
  ✓ Applications

Go prove some languages are not regular!
""")