L₁ = {w∈{a,b}^* | w enthält das Teilwort ababab nicht.}

L₁ = {w∈{a,b}^* | $$\left|w\right|_a\ge\ 64$$ und $$\left|w\right|_b=2\ \left(mod\ 5\right)$$ .}

L₁ = {w∈{a,b}^* | $$\left|w\right|_a=0\ \left(mod\ \left|w\right|_b\right)$$ .}

L₄ = {bⁿaw∈{a,b}^* | $$n\ \in\ N$$ w enthält das Teilwort bⁿ nicht.}

Falls ein NEA mit 3 Zuständen existiert, welcher L akzeptiert, so gibt es auch einen deterministischen EA mit 8 Zuständen, der L akzeptiert.

Sei $$n_0$$ die Konstante, so dass das Pumping Lemma gilt. Dann existiert $$w\in\ L$$ mit $$\left|w\right|<n_0$$ .

Sei L'⊆Σ_bool^* endlich. Dann ist $$L\cup\ L'$$ regulär.

Für jedes x∈Σ_bool^* definieren wir $$L_x\ =\ \left\{y\ \in\ \Sigma\ _{bool^{ }}^{\cdot}\left|\ xy\ \in\ L\right|\right\}$$ . Dann ist nach Lemma 3.3 die Familie von Sprachen $$\left\{L_x\ \left|\ x\in\ \Sigma\ _{bool^{ }}^{\cdot}\right|\right\}$$ endlich.

Es existiert eine Konstante $$c_1\in\ N$$ , sodass für alle $$n\in\ N^+$$

$$K\left(x_n\right)\le\ \frac{1}{3}\left|x_n\right|+c_1$$

Für alle N∈ℕ existier ein n≥N, so dass $$x_n$$ zufällig ist.

Es existiert eine Konstante $$c_2\in\ N$$ , sodass für alle $$n\in\ N,\ n\ge2$$

$$K\left(x_n\right)\le\ \log_2\left(\left|x_n\right|\right)+c_2$$

Für alle $$c_3\in\ N$$ existiert ein N∈ℕ, sodass für alle n≥N gilt:

$$K\left(x_n\right)>2^{\frac{1}{3}c_3}$$

Für alle N∈ℕ existier ein n≥N, so dass:

$$K\left(x_n\right)>\lceil\ \log_2\left(n\right)\rceil\$$