Mathematik – die besten Beiträge

Kann man mir diese mathematische Notation erklären?

Ich bin kein Mathematiker und mit aussagelogischen Quantoren nicht bewandert: Es geht aber um das Folgende:

Eine Aussage der Informatik (Pumping Lemma) wird so beschrieben:

Ist L (eine formale Sprache) durch einen endlichen Automaten erkennbar,
dann gibt es ein p ∈ N
sodass für alle w ∈ L mit |w|≥p gilt: (w=Wortlänge)
Es gibt ein Zerlegung w = xyz mit y ≠ ε und |xy ≤ p
sodass für alle i ∈ N gilt: xy^iz ∈ L

Soweit so gut - obwohl ich sehr gut verstehe, was damit gemeint sein soll, habe ich nun doch ein seltsames Bauchgefühl:

Was ist, wenn die Sprache nur aus L={a} besteht? D.h. es gibt nur das Wort a. Dieses wäre ja erkennbar.

Welches p erfüllt hier aber die Aussage "für alle w ∈ L mit |w|≥p" ? p kann ja sinnvoll höchstens 1 sein. Also setzte ich p=1. Es gibt nun aber kein L mit |w|>1. Egal was ich für ein p nehme - es trifft nie zu: Dies ist dann zwar kein Widerspruch, nur ist es eine Aussage für die Elemente einer leeren Menge und dann sagt dieser Satz eine Trivialität aus. Eine Aussage kann sich ja sinnvollerweise nur auf etwas beziehen, das im Kontext vorhanden ist. Dieses Lemma macht doch eigentlich nur wirklichen Sinn, wenn es um Sprachen geht, die in in der Wortlänge grundsätzlich unbeschränkt sind (oder eine Wortlänge haben, die mindestens so groß ist, wie die Anzahl der Zustände im Automaten) - oder sehe ich da was falsch? Ich hab hier momentan einen kleinen Knoten im Hirn...

Mathematik, Informatik

Meistgelesene Beiträge zum Thema Mathematik