# Limitations of Regular Expressions

Take a deterministic finite state machine with states.

Suppose that a word of with is accepted by the machine. This means that the machine went through some state twice, say after reading and then after reading symbols of the word.

Then for some words with and we have where the state after reading and state after reading are the same. Then it means that the machine is in the same state after reading for any , so all words of the form are accepted by the machine.

This is a rough statement of the so called “pumping lemma”.

**Example of application:** The language is not regular. Suppose the contrary. Then there is a machine that accepts the language; let be the number of states of . The word is accepted by . While reading the prefix the machine must go through some state twice. If we skip this loop, then there is a word of the form for
that is also accepted, which is contradiction with the condition that accepts .