qraymo Garden

Powered by 🌱Roam Garden

PL

Aliases:: Pumping-Lemma

def Pumping-Lemma für reguläre Sprache

∀L⊆Σ∗ mit L\forall L \subseteq \Sigma^{*} \text{ mit } L regulär:

∃n∈Nforallw∈L, mit ∣w∣>nexistsu,v,x∈Σ∗ mit w=uvx,∣uv∣≤n,v≠εforalli∈N0:\uvix∈L\exists n \in \N \\forall w \in L, \text { mit } |w|>n \\exists u, v, x \in \Sigma^{*} \text{ mit } w = uvx, |uv| \leq n, v \neq \varepsilon \\forall i \in \N_{0}: \uv^{i}x \in L

Widerlegen der Aussage des Pumping-Lemmas beweist Nicht-Regularität einer Sprache

D.h. es ist zu widerlegen für eine geg. Sprache LL, 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

keine hinreichende Bedingung für die Regularität von Sprachen

[[Verallgemeintertes PL]]

Referenced in

PL