Ergebnis 1 bis 3 von 3
  1. #1
    Anfänger Avatar von BlackCobra
    Registriert seit
    04.08.2008
    Beiträge
    807

    Frage Verständnisproblem zum Pumping-Lemma

    Hallo,

    Ich habe wie der Titel schon sagt ein Problem mit dem Pumping-Lemma, für alle die es nicht kennen hier mal die Definition;

    Code:
    für jede reguläre Sprache L gibt es eine natürliche Zahl n, sodass gilt: Jedes Wort z in L mit Mindestlänge n hat eine Zerlegung z = uvw mit den folgenden drei Eigenschaften:
    
     
    
    1. Die beiden Wörter u und v haben zusammen höchstens die Länge n.
    2. Das Wort v ist nicht leer.
    3. Für jede natürliche Zahl (mit 0) i ist das Wort u(v^i)n in der Sprache L, d. h. die Wörter uw, uvw, uvvw, uvvvw, usw. sind alle in der Sprache L.
    Ich nehme jetzt mal die Reguläre Sprache L(r) die von dem regulären Audruck r = aabba über dem Alphabet Σ = {a,b} beschrieben wird als Beispiel.

    Für diese Reguläre Sprache (Sie kann durch einen regulären Ausdruck dargestellt werden) gibt es jedoch kein Wort z in L mit Mindestlänge n sodass ich es in drei Teile zerlegen könnte, und den Mittelteil wiederholen/weglassen könnte sodass das entstehende Wort immer noch in L liegt, da L nur aus einem einzigen Wort besteht.

    Was habe ich am Pumping-Lemma falsch verstanden?

    grüße BlackCobra (diesen Namen sollte ich unbedingt mal ändern)

  2. #2
    Der mit Anatidaephobie Avatar von blackberry
    Registriert seit
    11.07.2008
    Beiträge
    2.350

    Standard AW: Verständnisproblem zum Pumping-Lemma

    Du meinst die Sprache, die nur das Wort aabba enthält? Die genügt der Aussage des Pumping-Lemmas; wähle etwa n=6 in deiner Formulierung von oben.

    Der Punkt ist, dass All-Quantifizierungen über die leere Menge immer wahr sind. Beispielsweise die Aussage "Alle blauen Giraffen sind grün" ist wahr (vorausgesetzt, dass es keine blauen Giraffen gibt) -- denn die Negation dieser Aussage ("Es gibt eine blaue Giraffe, die nicht grün ist") ist ersichtlich falsch.

    PDFTT cr3w a.E. — ReiDC0Re, lindor, Sera, berry
    please do feed the trolls crew and elk
    Ehrenwerte Mitglieder im Ruhestand: OpCodez, SFX.
    "Was sich blackberry gerade denkt" — Vorsicht! Frei laufender Wahnsinn!
    Zitat von fuckinghot19: "PS: Blackberry ist auf FH der Trollkönig ^^."
    An dieser Stelle danke ich all meinen Fans und Hatern gleichermaßen ^.^

  3. Folgende Benutzer haben sich für diesen Beitrag bedankt:

    BlackCobra (30.07.2015)

  4. #3
    Anfänger Avatar von BlackCobra
    Registriert seit
    04.08.2008
    Beiträge
    807

    Standard AW: Verständnisproblem zum Pumping-Lemma

    Danke für die Antwort, man sollte sich solche Lemmas doch etwas genauer durchlesen als ich es getan habe, ich hatte die Stelle "Jedes Wort z in L mit Mindestlänge n" komplett übersehen

Ähnliche Themen

  1. [PS] "pumping heart" Animationsvideotut
    Von script-kiddy im Forum GFX Tipps & Tutorials
    Antworten: 11
    Letzter Beitrag: 01.03.2009, 16:45

Berechtigungen

  • Neue Themen erstellen: Nein
  • Themen beantworten: Nein
  • Anhänge hochladen: Nein
  • Beiträge bearbeiten: Nein
  •