Theoretische und technische Informatik - ganz praktisch - Letzte Fragen & Antworten in 2014-N-03

Beantwortet: Beweisführung bei PPL

Sat, 04 Jan 2020 17:26:40 +0000

1. wenn du mit (111111)⁶ das Wort mit 46 Einsen meinst, dann nicht. Es sind nämlich nur die Wörter mit 3, 9, 81, 6561 … Einsen teil der Sprache. Die Anzahl der Einsen des vorherigen Wortes quadriert ergibt nämlich die Anzahl der Einsen des nächsten Wortes.

2. So wie ich die Lösung verstehe wurde in diesem Beispiel kein bestimmtes Wort gewählt, da dies für alle Wörter der Sprach gezeigt werden kann (wir machen ja eine Abschätzung und sagen es gillt bereits für das 2. Wort nicht mehr wenn vom ersten ausgehen, damit kann es für alle anderen auch nicht gehen). Bei den Beispielen im Tutorium war es wichtig eine „bestimmte Art von Wörtern“ der Sprach zu verwenden. Je nach dem welches Wort wir dort gewählt haben konnte es sein, dass wir durch Pumpen keinen Widerspruch zeigen konnten.

3. ja, es wurde gezeigt, dass mindestens das 3-Fache benötigt wird um ein neues Wort zu generieren, das gilt aber nur um auf das 2. Wort zu kommen. Danach wird bereits das 9-Fache benötigt, dann dass 81-Fache etc. Das 2-Fache kann daher auf keinen Fall ausreichend sein, genau so wie z.B. das 0-Fache. Beim Pumping Lemma kann meist für verschiedene i gezeigt werden, dass das Wort nach dem Pumpen nicht mehr Teil der Sprache ist. Da wir einen Widerspruchsbeweis führen reicht jedoch ein einziges Gegenbeispiel.

Viele Grüße,

Sören (Tutor)

Alternative Lösung

Thu, 12 Jul 2018 17:37:11 +0000

Wäre es hier auch möglich über das Wort $1^{3^{2^{n}}}$ mit $n\in \mathbb{N}$ zu zeigen, dass $L\not\in L_{3}$ ?

Vielen Dank!!

Beantwortet: Weshalb ist das kleinste Wort 111

Sun, 24 Jul 2016 07:57:36 +0000

Wenn Sie genau hinsehen, sehen Sie, dass da nicht steht L={1}*, sondern L⊂{1}* (echte Teilmenge der Menge der Wörter, die aus beliebig vielen Einsen bestehen).

Die Sprache L selbst ist rekursiv definiert durch das Wort 111 und bestimmte Vielfache der Worte, die bereits in L sind (beginnend mit 111, das damit das kürzeste Wort in L sein muss).

Viele Grüße,

Micaela Wünsche

Beantwortet: Erklärung von Widerspruch

Sun, 14 Feb 2016 14:48:07 +0000

Hallo uwdqk,

ich versuche das ganze mal etwas ausführlicher zu formulieren.

Um den Widerspruch zu zeigen wurde in diesem Bespiel für die Pumpvariable i=2 gewählt. Wir betrachten also den Fall |xy²z|.

Als nächstes schätzen wir die Länge des gepumpten Wortes nach oben ab.

Da nach (1) |xy|<=n ist, kann |y| maximal n Zeichen lang sein, also das komplette Wort enthalten ( x und z sind leer). Für i=2 kann sich die Wortlänge maximal verdoppeln, was durch |xy²z|<= 2 |w| dargestellt wird.

Wenn wir uns jetzt die Sprache L anschauen, stellen wir fest, dass 111 das kleinste Wort in L ist und die Länge 3 hat ( die Wortlänge |w| ist also für alle Wörter größer oder gleich 3 ). Demnach unterschieden sich auch alle anderen Wörter der Sprache mindestens um den Faktor 3, weil w^|w| gilt. das bedeutet aber einen Widerspruch für i=2, da wir hier maximal einen Unterschied um den Faktor 2 haben. Demnach kann L nicht vom Typ 3 sein.

Viele Grüße

Gregor (Tutor)

Beantwortet: Pumping Lemma- alternative Begründung richtig?

Sat, 30 Jan 2016 19:10:55 +0000

Nein, das geht nicht, denn Ihr Wort hat nicht die Länge $|w|\geq n$. (Das ist sehr wichtig und ein häufiger Fehler, bitte beachten Sie das in der Klausur!)

Außerdem dürfen Sie die Zerlegung nicht wählen, sondern müssen über alle möglichen Zerlegungen argumentieren!

Viele Grüße

Lukas König