Home     
    
    Bücher   Links   Impressum

next up previous contents
Nächste Seite: Abschlußeigenschaften Aufwärts: Kontextfreie Sprachen (CFG) Vorherige Seite: CYK-Algorithmus für das Wortproblem   Inhalt

Unterabschnitte

Pumping Lemma für kontextfreie Sprachen

Satz

Sei $L$ eine kontextfreie Sprache. Dann gibt es eine natürliche Zahl $n$, so daß sich jedes Wort $z\in L$ der Länge $\geq n$ wie folgt zerlegen läßt: $z=uvwxy$, wobei
  1. $\vert vx\vert\geq 1$
  2. $\vert vwx\vert\leq n$
  3. $uv^{k}wx^{k}y\in L$ für alle $k\in\mathbb{N}$.

Beweis

Siehe Literatur.