Math and science::Theory of Computation
Pumping lemma for regular languages
The pumping lemma is useful for showing that a language cannot be represented by a finite state machine.
Can a language be accepted by an automaton?
There are two cases.
- If a language contains only finite strings, we can create a finite automaton that handles each case.
- If a language contains infinite strings, we look to the pumping lemma to answer this question.
The gist of the lemma
The gist of the pumping lemma is: if a finite set of states is able to represent an infinite string, then during the state transitions between start and accept states, there must be a [...] at some point. This property can be used to show, by contradiction, that some languages cannot be represented by finite state automata.
If \( A \) is a regular language, then there is a number \( p \) (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 three conditions:
- for each \( i \ge 0, xy^iz \in A \)
- \( |y| \ge 0 \)