Die Sprache \(L\) ist nicht regulär, wie man mit dem Pumping-Lemma zeigen kann (bedenke, dass der Automat eine Art "Gedächtnis" haben müsste). Sei vorab noch erwähnt, dass im Folgenden \(|x|_y\) die Anzahl der Vorkommen von \(y\) in \(x\) zählt. Sei \(n\in\mathbb{N}\). Zunächst stellen wir fest, dass \(\forall v\in L\) mit \(|v|\equiv 0\mod 2\) und \(v=v'v''\) mit \(|v'|=|v''|=\frac{|v|}{2}\) gilt:
$$|\mathrm{even}(v')|_1+|\mathrm{even}(v'')|_1=|\mathrm{even}(v)|_1=|v''|_1=|\mathrm{even}(v'')|_1+|\mathrm{odd}(v'')|_1$$ Durch Hinsehen erkennt man direkt, dass \(|\mathrm{even}(v')|_1=|\mathrm{odd}(v'')|_1\). Völlig analog ist \(|\mathrm{odd}(v')|_1=|\mathrm{even}(v'')|_1\) und folglich $$|v'|_1=|\mathrm{even}(v')|_1+|\mathrm{odd}(v')|_1=|\mathrm{even}(v'')|_1+|\mathrm{odd}(v'')|_1=|v''|_1$$Alle Wörter \(w_i\in L\) mit \(|w_i|\equiv 0\mod 2\) haben folglich in der ersten und zweiten Hälfte jeweils dieselbe Anzahl an Einsen. Das Pumping-Lemma setzen wir nun dazu ein, um zu zeigen, dass diese Eigenschaft nicht erhalten bleiben kann und die Sprache somit nicht "pumpbar" ist. Sei \(n\in\mathbb{N}\), \(2^k=n'\geq n\) eine Zweierpotenz und \(w\in L\) mit \(|w|=2n'+2\). Sei $$\mathbb{I}:=\left\{2^0+1,2^1+1,...,2^k+1\right\}\cup\left\{2^0+2^k+1,2^1+2^k+1,...,2\cdot 2^k+1\right\}$$ eine Indexmenge. Wir stellen folgende Anforderung an unser (wohl überlegt) ausgewähltes Wort: $$w_i=1\Longleftrightarrow i\in\mathbb{I}$$ Es ist \(w=\mathrm{odd}(w)\cdot \mathrm{even}(w)\in L\). Zudem ist das letzte Zeichen der ersten und das erste Zeichen der zweiten Hälfte jeweils eine \(1\). Wir zerlegen \(w\) beliebig, also \(w=uvr\) mit \(|uv|\leq n\) und \(v\neq \epsilon\). Dann ist aber \(uv^0r\notin L\), da es mehr Einsen in der zweiten als in der ersten Hälfte besitzt. Wir haben also einen Weg gefunden für alle \(n\in\mathbb{N}\) ein Wort \(w\in L\) zu konstruieren, für das keine Zerlegung gemäß dem Pumping-Lemma existiert.
\(L\) ist somit nicht regulär \(\square\)
