Theoretische und technische Informatik - ganz praktisch - Letzte Fragen & Antworten in 2011-B-01

Beantwortet: Alternatives Pumpwort w = a^n b^m c^(m+n)

Tue, 07 Jan 2020 20:19:04 +0000

Hallo uipmv,

Bei dem PPL versuchen wir immer, unsere Testwort mit nur einer Variablen auszudrücken (in der Lösung zum Beispiel unser "n"). Dadurch wird zum Beispiel unsere Bedingung |w| >= n leichter zu überprüfen. Ich würde also empfehlen lieber Testwörter solcher Form zu verwenden. Da ich aber nichts widersprüchliches finden konnte bezüglich der Frage, ob auch eine zweite Variable im Testwort vorkommen darf, sollte Ihre Alternativlösung auch funktionieren.

Viele Grüße

Alex (Tutor)

Beantwortet: Verständnis von s2-Übergängen

Sat, 19 Jan 2019 17:54:55 +0000

Hallo uvlpj,

diese Zustandsüberführungen entleren den Keller.

Mit δ(s1, c, a) = (s2, λ) und δ(s1, c, b) = (s2, λ) erkennt das Automat, dass genau die Hälfte des Wörtes bearbeitet wurde und löscht das letzte im Keller gelegte Zeichen und die erste c. Mit der von dir genannte Zustandsüberführungen werden alle Weitere Zeichen gelöscht. Nur wenn das Wort fertig bearbeitet wurde und gleichzeitig den Keller leer ist, wird das Wort akzeptiert.

Viele Grüße,

Natalie (Tutorin)

Beantwortet: Pumping-Lemma alle Zerlegungen?

Mon, 15 Jan 2018 16:57:08 +0000

Sie meinen die Formulierung "Nach dem PPL existiert eine Zerlegung w = xyz mit..."?

Das bezieht sich auf die ANNAHME, das PPL wäre in diesem Fall anwendbar. Das führen wir im Anschluss zum Widerspruch, und bei der Negation wird aus dem "Existiert" ein "Für alle".

Beantwortet: Bonus11, A1a, andere Lösung möglich?

Sun, 14 Jan 2018 18:21:25 +0000

Hallo,

zu 1)

Die Antwort findet sich im Volesungsfoliensatz 3 auf Folie 16 oder auch in den Tutoriumsfolien Foliensatz Nr. 3 auf Folie 19.

"Bei allen Typen außer Typ 1, sind auch Übergänge A -> \lambda erlaubt."

zu 2)

Ich kann keinen Fehler entdecken.

Viele Grüße

Alex (Tutor)

Beantwortet: Nun hier könnte man doch den Spieß umdrehen?

Sat, 10 Oct 2015 18:55:06 +0000

Hallo,

1) Deine PL Aussage ist nicht korrekt. Der erste Punkt müsste heißen:

|xy|<=n

2) Wie du oben sagst, überprüft man alle möglichen Zerlegungen, du aber überprüfst nur Zerlegungen mit

yz=b^j c^2j

Das ist nicht beliebig. Du sagst es muss doppelt so viele c's wie b's enthalten. Außerdem dürfte mit deinem Fehler 1) dein yz nur aus c's bestehen, da es das Ende vom Wort ist und maximal n-stellen nach links reicht. Dein gewähltes Wort hat aber 2n c's am Ende.

Schau die Definition nochmal genauer an und/oder frag deinen Tutor im Tut, falls du nicht weiter kommen solltest.

Gruß,

Adam (Tutor)

Beantwortet: Gibt es hier Punktabzug wenn man noch ein zusätzliches A einführt?

Sat, 10 Oct 2015 18:54:03 +0000

Es gibt immer mehrere richtige Lösungen, deine enthält zwar eine (nicht notwendige) Umbennung, aber ist genauso richtig.

Grüße,

Melanie (Tutorin)