ContentsPrevNext

Summary of Facts Found

• For every fsa and every string with at least as many symbols as there are states in the fsa (number of symbols >= number of states), there will be at least one repeat of a state in the fsa.
• The portion of the string that gets from that state and back to that state (called y) can be repeated or can be omited.

These facts can be formally stated in the following way:

The Pumping lemma

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

1. for each i >= 0 xyⁱz is an element of A
2. |y| > 0
3. |xy| <= p

Pumping 10