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\)