Skip to content

6. Pumping Lemma

Jan 25, 2022

Non-regular languages

  • every finite language is regular vacuously: create path for every string in the NFA

  • also automatically regular:   \(a^*b\)     \(b^*c + a\)     \(b+c(a+b)\)

  • non-regular languages are infinite in size and not describable by FA or RE

  • non-regular language example: \(\{a^nb^n:n \geq 0\}\)

    • note: this is a subset within regular language \(a^*b^*\)
    1
2
3
4
      ╭──────╮
  │     -------- a*b*   regular
  │ □ ---------- aⁿbⁿ  non-regular
  ╰──────╯

  • in general: non-regular languages are a subset of regular language

    • the non-regular language is more restricted => more difficult to recognize

  • when \(L\) is non-regular then there exists no FA or RE accepts \(L\)
    => prove using pumping lemma

Pumping Lemma

  • idea: for some long string \(w\), automaton state is repeated in the walk \(w = \sigma_1\sigma_2...\sigma_k\) due to pigeonhole principle

    • number of transitions: \(|w|\)

    • number of states needed to process the string : \(|w| + 1\)

    • if \(|w| \geq p\), where \(p\) is number of states in DFA, some state \(q\) must be repeated

  • We can write \(w = xyz\) where

    • \(y\) is the substring between the first and second occurrence of \(q\)

    • \(|xy| \leq p\)   note: states in \(xy\) are unique since no state is repeated except \(q\)

    • \(|y| \geq 1\) since there is at least 1 transition in the loop

    • \(z\) can be anything and can overlap with paths within \(xy\)

    • accepted strings, in general: \(xy^iz \in L\), \(i=0,1,2,...\)

      • string \(xz\) is accepted => does not loop since \(|y| = 0\)

      • also: \(xyyz, xyyyz, ...\), etc.

Definition

Given infinite regular language \(L\), there exists integer \(p\) (critical length, pumping length) for any string \(w \in L\) with length \(|w| \geq p\), we can write \(w = xyz\) with \(|xy| \leq p\) and \(|y| \geq 1\) such that \(xy^iz \in L\), \(i=0,1,2,...\)

Applications

  • Prove by contradiction that infinite language \(L\) is not regular

    • Assume \(L\) is regular, then the pumping lemma should hold for \(L\)

    • Use pumping lemma to obtain a contradiction

      • Let \(p\) be the critical length for \(L\)
      • Choose a string \(w \in L\) which satisfies the length condition \(|w| \geq p\)
      • write \(w = xyz\)
      • show that \(w' = xy^iz \notin L\) for some \(i \neq 1\)
      • this gives a contradiction since by pumping lemma \(w' = xy^iz \in L\)

    • Therefore \(L\) is not regular

  • It is sufficient to show only one string \(w \in L\) yields a contradiction

Example Proof

Prove that \(L = \{a^nb^n:n \geq 0\}\) is not regular

  1. Let \(p\) be critical length for \(L\), pick a string \(w\) such that \(w \in L\) and length \(|w| \geq p\)
    Here we pick \(w = a^pb^p\)

  2. Identify substring \(y\): we can write \(w = a^pb^p = xyz\) with lengths \(|xy| \leq p\) and \(|y| \geq 1\) thus \(y = a^k, 1 \leq k \leq p\)

    1
2
3
4
5
           p         p 
|¯¯¯¯¯¯¯¯¯¯¯¯¯||¯¯¯|
a...aa...aa...ab...b   <--- aᴾbᴾ
|___||___||________| 
  x    y       z

  3. for regular language, repeating of removing \(y\) still gives something that is in the language => from the pumping lemma, \(xy^2z \in L\) thus \(a^{p+k}b^{p} \in L\) where \(k \geq 1\)

    1
2
3
4
5
             p+k          p 
|¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯||¯¯¯|
a...aa...aa...aa...ab...b   <--- aᴾ⁺ᴷbᴾ
|___||___||___||________| 
  x    y    y      z

  4. But \(L = \{a^nb^n:n \geq 0\}\) therefore \(a^{p+k}b^{p} \notin L\) => contradiction

  5. Conclusion: \(L\) is not a regular language