Automata and Grammars, Pumping lemma

08 November 2026

In this log entry I will go over the basics of the pumping lemma. Walk through an example problem to showcase how it can be used in practice to determine the regularity of a formal language.

Let's start with a pumping lemma, which says that if L is a regular formal language, then there exists a natural number p which is 1 or greater such that every word w from the regular formal language L with length of at least p can be written as w=xyz, where x,y,z are strings over the alphabet, where x and z can be epsilon, |xy| is upmost p, |y| is 1 or greater and xy^(k)z belongs to L for every k zero or greater.

So esentially we're able to prove, that a language is not regular and that by choosing a word (bigger than p, so in relation to some parameter), we'll find all divisions in three parts (smaller than p), we'll find an adequate k.

L_{1.5} = {a^{i} b^{j} c^{k} | i, j, k \in ℕ_{0}, i, k \geq 0, j \geq 2, i + k = j}

Let's have this as an example. We want to determine, if this langauge is or is not regular. It describes a language that can have zero a's and c's, but there has to be at least at least two b's. The addition of i and k must be j which means i and k can not be both zero nor one being one and the other zero.

We can first try solving it intuitively. One way of looking onto the problem is through an automaton. If for the given language existed a finite automaton, it would contain cycles. That means cycles could be gone through as many times as wished. That is the division on x-y-z and the y can be set on whichever "i". x.y^k.z still has to be within the language.

Now we can apply it to this problem. When we get to the state when we have generated all the "a" and "b", there exists only one way to fill in "c". The automaton would have to remember how many a's the has read, so it can check b's against them. I can not generate it as many times as we would like. All words of L has the form of $a^{r} . b^{r + s} . c^{s}$ and now we have to look into the proof to figure out, what exactly we're after. The second paragraph rewritten as a formulae:

L is regular \Rightarrow (\exists p \in ℕ, p \geq 1) (\forall w \in L) [| w | \geq p \Rightarrow (\exists x, y, z \in Σ^{*}) (w = x y z \land | x y | \leq p \land | y | \geq 1 \land (\forall k \geq 0) : x y^{k} z \in L)]

We will choose any "p", via this "p" we'll define our word. So what we need is a word longer than "p" such that for each "p" will something hold true. We can choose $a^{p} . b^{2 p} . c^{p}$ We'll divide the state of "p" into three parts. The first is when |xy| is smaller than "p". In this scenario, the only option is x=epsilon, y=a^p, z=b^(2p).c^p. And here when we do y^0, then the word will certainly not be in the language, because a^0-b^2.c^1 is not in the language. Now we need to find all possible divisions that comply with the requirement y!=epsilon, |xy|<=p and here the division is only one, x=a^k, y=a^(p-k), z=b^(2p).c^p. Now let's say that if the language was regular, then for any "p" in at least one found divisions xyp, we could choose any "i" in "xy^iz" and the word would still be in the language. However, we can choose y=0 and then we get word (a^k).(a^(p-k))^0.(b^2p.c^p), which is a^k.b^2p.c^p and this word does not belong to the language.

We have proved that the language is not regular via the pumping lemma.