Theoretische und technische Informatik - ganz praktisch - Letzte Fragen & Antworten 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)

Beantwortet: Beziehung zu |z| >= n

Thu, 07 Feb 2019 20:33:58 +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.

Beantwortet: Pumpen mit i=0

Wed, 01 Feb 2017 10:04:09 +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.

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)

Beantwortet: Pumpinglemma Widerspruchsbeweis

Wed, 22 Oct 2014 11:00:54 +0000

Das ist genau dieselbe Vorgehensweise wie in der Musterlösung, nur dass wir nicht auf die Gleichmächtigkeit von rechtslinearen Grammatiken und EA verwiesen haben. Insofern ist Ihre Lösung sogar etwas genauer :-)

Viele Grüße

Lukas König

Beantwortet: Pumpinglemma Gegenbeispiel

Wed, 22 Oct 2014 10:58:16 +0000

Hallo,

du musst für alle möglichen Zerlegungen deines Wortes (das du dir ja aussuchen darfst, solange es länger als n und Teil deiner Sprache ist) ein i finden, das zu einem Widerspruch führt.

Deshalb wird auch in vielen Aufgaben eine Fallunterscheidung gemacht, deren Fälle alle möglichen Zerlegungen abdecken und dann für jeden dieser Fälle ein i gefunden, das zu einem Widerspruch führt.

Viele Grüße

Lukas (Tutor)