Theoretische und technische Informatik - ganz praktisch - Letzte Aktivität in PUM-AF

Beantwortet: alternativ

Sat, 22 Jan 2022 15:00:05 +0000

Hallo,

ich bin mir nicht sicher, was du mit IyI => 1 meinst. Könntest du das konkretisieren?
Und anstatt 0^(...) müsste es bei der Aufgabe a^(...) heißen, dann funktioniert es auch mit xy=a^j 1<=j<=n, y=a^k 1<=j<=n und z dann entsprechend (wie in der Lösung)

Antwort ausgewählt: Beziehung zu |z| >= n

Sat, 09 Feb 2019 11:17:36 +0000

Hallo,

das muss auch nicht gelten für i=0, wie du ja schon geschrieben hast, die Schleifen müssen nicht durchlaufen werden.

Die Sprache muss Pumpstellen haben (sonst könnte man nur endlich viele Wörter erzeugen).

Die Idee dahinter ist eine andere: Du nimmst ein Wort z, das mindestens n Zeichen lang ist. Dies ist die Vorraussetzung.
Dein gewähltes Wort z beinhaltet also auch eine Pumpstelle, sonst wäre es nicht mindestens n Zeichen lang. Die Schleife muss aber nicht zwangsläufig durchlaufen werden (i=0), dann ist das modifizierte Wort möglicherweiße kürzer als n Zeichen, aber es muss immer noch zur Sprache gehören, da man die Pumpstelle (von z) beliebig oft pumpen kann (i=0,1,2,...).
Also ist die Grundlage nicht hinfällig, da immer noch gilt |z| >= n.

Das selbe Prinzip gilt auch bei dem PPL für reguläre Sprachen.

Ich hoffe es ist nun klarer, wenn du noch Fragen hast kannst du gerne noch einmal schreiben.

Viele Grüße
Anne (Tutor)

Beantwortet: Zerlegung

Thu, 02 Feb 2017 11:26:53 +0000

Hallo,

ersteinmal steht auch in der Lösung, dass die angegebene Sprache keine rechtslineare Sprache ist. Insofern ist Ihr Ergebnis korrekt.

Sie haben jedoch methodisch eine Unsauberkeit, da Sie (denke ich) festlegen, dass j+k=n. Dies ist jedoch nur eine der Zerlegungen, die die Bedingung

1) |xy| <= n

erfüllt ( und zwar genau der Fall: |xy|=n).

Wir wollen beim Pumping-Lemma erst alle möglichen Zerlegungen des Wortes betrachten, die die 3 Bedingungen erfüllen und dann zeigen, dass diese Zerlegung im konkreten Fall durch Wahl der Pumpvariable i nicht mehr in L liegt.

Antwort bearbeitet: Pumpen mit i=0

Wed, 01 Feb 2017 10:10:13 +0000

Nein. Lassen Sie uns das mal präzise formulieren:

Die Länge von $y$ ist $|y|$, und diese muss größergleich eins sein, also darf $y$ nicht leer sein. Äquivalent schreiben wir deshalb manchmal auch $y \neq \lambda$. $y^0$ ist aber ein ganz anderer Ausdruck als $y$, über den in den Eigenschaften des PPL nichts ausgesagt wurde. Dieser kann (im Sinne von "darf") prinzipiell beliebig viele Zeichen enthalten - in diesem Fall hat er eben 0.

Das ist so, wie die beiden Aussagen "Auf Landstraßen gilt eine Maximalgeschwindigkeit von $v=100$ km/h" und "die Geschwindigkeit $v$ geteilt durch zwei ist eine gute Abschätzung für den Mindestabstand" (laut ADAC ) ganz normal nebeneinander stehen können.

Bearbeitet: Pumpinglemma Gegenbeispiel

Wed, 22 Oct 2014 11:07:27 +0000

Hallo:)

Muss ich denn allgemein beim PPL für Sprachen immer alle Gegenbeispiele geben oder reicht auch schon ein Gegenbeispiel aus?

Dankeschön

Bearbeitet: Pumpinglemma Widerspruchsbeweis

Wed, 22 Oct 2014 11:07:05 +0000

Hallo,

Ich bin bei der Aufgabe so vorgegangen das ich am Anfang auf die Gleichmächtigkeit von rechtslinearen Grammatiken und EA verwiesen habe. Und hab den Widerspruchsbeweis dann mit dem PPL für EA-Sprachen geführt. Wäre das auch korrekt?

Viele Grüße

Beantwortet: Pumpinglemma

Wed, 22 Oct 2014 11:05:26 +0000

y != lambda und y >= 1 bedeuten das selbe, da jedes nicht leere Wort y mindestens ein Zeichen haben muss, also |y| >= 1. Umgekehrt kann ein Wort mit mindestens einem Zeichen nicht leer sein.

Gruß,

Tobias (Tutor)

Beantwortet: Fallunterscheidung

Wed, 22 Oct 2014 11:03:45 +0000

Wir wissen wegen der Bedingung |xy|<=n, dass das Teilwort xy nur aus a's bestehen kann. Deshalb kommen anderen Varianten für xy gar nicht in Frage.

Gruß Jörg (Tutor)