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...
ich finde es hier doof, dass man seinen eigenen Beitrag nicht korrigieren kann und immer auf die Gnade von Moderatoren angewiesen ist, die das irgendwann nach ein paar Stunden erledigen...
Es muss natürlich heißen:
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) gilt:
Es gibt ein Zerlegung w = xyz mit y ≠ ε und |xy ≤ p
sodass für alle i ∈ N gilt: xy^iz ∈ L
Und dann meinte ich:
Also setzte ich p=1. Es gibt nun aber kein L mit |w|>1.
3 Antworten
(w=Wortlänge)
w ist nicht die Wortlänge, sondern das Wort. Die Wortlänge wird durch den Operator |.| bestimmt.
Welches p erfüllt hier aber die Aussage "für alle w ∈ L mit |w|≥p" ?
Ein beliebiger Wert größer 1.
Ich musste auch erst einmal überlegen, aber wenn du es ausprobierst siehst du, dass das vollkommend valide ist.
Ja, es ist eine valide Aussage, nur macht der Satz für Sprachen mit endlicher Wortlänge keinen wirklichen Sinn.
Eine wirkliche Information erhälst du sowieso erst, wenn das Lemma nicht erfüllbar ist. Dann wäre die Sprache nämlich nicht regulär.
Wenn das Lemma aber erfüllt ist, dann kann die Sprache regulär sein, muss sie aber nicht.
verstehe - ich bin einfach nicht geübt im Umgang mit Formalismen. Dass es kein Widerspruch ist, war mir von Anfang an klar, mich hat das nur nur irritiert...
Das pumping lemma ist nicht auf deine Sprache L anwendbar und damit ist L keine reguläre Sprache.
hmmm.
Verstehe ich nicht: Die Sprache L={a}, die nur aus einem Wort besteht ist doch regulär: Der endliche Automat besteht aus einem Anfangszustand und einem Übergang für a in den akzeptierenden Endzustand.
Oder nicht? Dann würde ich das gerne verstehen...
Stimmt, aus prädikatenlogischer Sicht ist der Fall trivial (bel. p in N). Grund hierfür, dass man den Fall trotzdem berücksichtigt ist lediglich, dass man ein notwendiges Kriterium für reguläre Sprachen haben möchte. Man könnte die Aussage für endliche Sprachen separat behandeln, aber in der Logik ist es einfach praktisch und ästhetisch, möglichst simple Aussagen zu bilden, welche den Geltungsbereich auf das Maximum ausdehnen.
Semantisch zeigt es aber auch gut den Umstand, dass das Aufpumpen ein Prinzip ist, was nur bei unendlichen Sprachen auftreten kann.
ja, sorry vertippt. Korrigieren darf man hier ja selbst nicht bzw. man ist auf die Gnade eines Moderators angewiesen, der sich i.A. nicht mal auskennt. Mich nervt das echt schon...
Ja, es ist eine valide Aussage, nur macht der Satz für Sprachen mit endlicher Wortlänge keinen wirklichen Sinn. Erst wenn eine Sprache aufpumpbar ist (und somit eine unbegrenzte Wortlänge haben kann) macht es Sinn. Das meinte ich.