Widerlegen der Aussage des Pumping-Lemmas beweist Nicht-Regularität einer Sprache
D.h. es ist zu widerlegen für eine geg. Sprache LLL, dass:
∀n∈Nexistsw∈L, mit ∣w∣>nforallu,v,x∈Σ∗ mit w=uvx,∣uv∣≤n,v≠εexistsi∈N0:\uvix∉L\forall n \in \N \\exists w \in L, \text { mit } |w|>n \\forall u, v, x \in \Sigma^{*} \text{ mit } w = uvx ,|uv| \leq n, v \neq \varepsilon \\exists i \in \N_{0}: \uv^{i}x \notin L∀n∈Nexistsw∈L, mit ∣w∣>nforallu,v,x∈Σ∗ mit w=uvx,∣uv∣≤n,v=εexistsi∈N0:\uvix∈/L
keine hinreichende Bedingung für die Regularität von Sprachen
Sprache ist nicht regulär ⇐:\Leftarrow:⇐: PL ist nicht erfüllt