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.

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 = x y z$ , satisfying the following three conditions:

for each $i \geq 0, x y^{i} z \in A$
$| y | \geq 0$
[...]

24.03.2020