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^{\ast }b$     $b^{\ast }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^n{b}^n:n\ge 0\}$

  • note: this is a subset within regular language $a^{\ast }{b}^{\ast }$

    ╭──────╮
    │     -------- 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|\ge 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|\le p$   note: states in $xy$ are unique since no state is repeated except $q$

  • $|y|\ge 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: $x{y}^{i}z\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|\ge p$, we can write $w=xyz$ with $|xy|\le p$ and $|y|\ge 1$ such that $x{y}^{i}z\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|\ge p$
    • write $w=xyz$
    • show that $w^{\prime }=x{y}^{i}z\notin L$ for some $i\ne 1$
    • this gives a contradiction since by pumping lemma $w^{\prime }=x{y}^{i}z\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^n{b}^n:n\ge 0\}$ is not regular

1. Let $p$ be critical length for $L$, pick a string $w$ such that $w\in L$ and length $|w|\ge p$
   Here we pick $w=a^p{b}^p$

2. Identify substring $y$: we can write $w=a^p{b}^p=xyz$ with lengths $|xy|\le p$ and $|y|\ge 1$ thus $y=a^k,1\le k\le p$

          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, $x{y}^{2}z\in L$ thus $a^{p+k}{b}^p\in L$ where $k\ge 1$

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

4. But $L=\{a^n{b}^n:n\ge 0\}$ therefore $a^{p+k}{b}^p\notin L$ => contradiction

5. Conclusion: $L$ is not a regular language