home

Pumping lemma

If \(A\) is a regular language, then there is a number \(p\) (the pumping length) where is \(s\) is any string in \(A\) that is at least length \(p\), then \(s\) may be divided into three pieces, \(s=xyz\), satisfying the following conditions:

  1. for each \(i \geq 0\), \(xy^iz \in A\)
  2. \(|y| \gt 0\)
  3. \(|xy| \leq p\)