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.

1. If a language contains only finite strings, we can create a finite automaton that handles each case.
2. 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.

### Pumping lemma

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:

1. for each $$i \ge 0, xy^iz \in A$$
2. $$|y| \ge 0$$
3. [...]