Theoretische und technische Informatik - ganz praktisch - Letzte Fragen & Antworten in AU-1-3

Beantwortet: Moore-Automaten

Thu, 06 Jan 2022 10:07:54 +0000

Hallo uqyws,

ja du hast recht, das müsste ein s0 anstatt a sein.

Viele Grüße

Anne (Tutorin)

Beantwortet: Auch Pump-Variable i=0 möglich?

Tue, 09 Jan 2018 10:56:34 +0000

Hey,

deine Lösung stimmt ebenfalls. Beim PPL genügt es eine Pumpvariable i zu finden für welche die Zerlegung deines Wortes eben nicht mehr in der Sprache enthalten ist. Häufig ist dies für kleine Werte von i bereits der Fall (0, 1, oder 2).

Wie du bereits geschrieben hast ist dies eben auch für i=0 der Fall, da k>=1 ist.

Viel Erfolg weiterhin!

Viele Grüße,

Marius (Tutor)

Beantwortet: Wäre diese Lösung auch als Beweis ausreichend

Thu, 11 Feb 2016 15:29:22 +0000

Hallo uedqa,

um mit Hilfe des Pumping-Lemmas zum Widerspruch zu kommen, müssen wir immer ALLE möglichen Partitionen betrachten, d.h. du darfst dir nicht eine beliebige Belegung von x,y,z suchen und dies zum Widerspruch führen. Daher führen wir auch die Variabeln j und k ein und zeigen den Widerspruch für alle Möglichkeiten. Eingeschränkt wird j und k nur durch unsere ersten beiden Bedingungen des Pumping-Lemma.

Deine Lösung ist also nicht ausreichend um zu zeigen, dass die Sprache nicht vom Typ 3 ist.

Viele Grüße,

Tim

Beantwortet: Nach welchen Kriterien wähle ich die Pumpvariable?

Wed, 25 Nov 2015 13:28:56 +0000

Hallo,
die Pumpvariable finden wir tatsächlich nur durch ausprobieren oder "logisches überlegen". In den meisten Fällen sollte es aber reichen mit niedrigen einstelligen Variablen zu testen.
Viele Grüße,
Janina (Tutorin)

Beantwortet: Welches Wort wird durch "uu" dargestellt?

Tue, 22 Sep 2015 08:56:35 +0000

"u" kann aus einer beliebigen Reihenfolge von 1 und 0 bestehen, z.B. 0011011

"uu" wäre also 00110110011011

Bei unserer Aufgabe wählen wir das Wort \( 0^n 1^n 0^n 1^n \), um zu beweisen, dass es keinen endlichen Automaten gibt der L7 erkennt.

Dies bedeutet aber nicht, dass die Sprache nur Wörter der Form \( 0^n 1^n 0^n 1^n \) erzeugt.

Du könntest auch das Wort \( 0^n 1^n 0^n 1^n \) wählen, um zu beweisen, dass es keinen endlichen Automaten gibt der L7 erkennt.

Ich hoffe das war verständlich soweit,

Grüße,

Julian (Tutor)

Beantwortet: Könnte man auch ein anderes Worrt wählen?

Tue, 22 Sep 2015 08:54:45 +0000

Das Wort = \(0^n 1^n 0^n 1^n\) ist zwar willkürlich gewählt, aber du kannst nicht das wort \(0^n 1^n\) wählen. Da dieses Wort nicht der Grammatik entspricht. Dein Wort kann nicht in zwei identische Teile aufgeteilt werden. Es sind folgende Worter erlaubt aabbaabb oder abcabc.

Alexander (Tutor)

Beantwortet: Welche Aussagen könnte man treffen, wenn man zum Schluss keinen Widerspruch hätte?

Tue, 22 Sep 2015 08:49:48 +0000

Richtig! Mit einem PPL kann man nur beweisen, dass eine Sprach nicht vom Typ 3 (bzw. 2) ist, indem man einen Wiederspruch zu den Annahmen findet. Wenn du keinen Wiederspruch findest, kannst du keine weiteren Aussagen treffen.

Gruß

Lukas (Tutor)

Beantwortet: Warum ist 0
Tue, 22 Sep 2015 08:46:36 +0000

Die Schreibweise in der Lösung ist nicht ganz eindeutig. Dort steht \( 0 < j, k \leq n \). Das soll heißen, dass \( 0 < j \leq n\) UND \( 0 < k \leq n\).

Ich hoffe, das löst dein Problem :)

Christiane (Tutor)

Beantwortet: Wie kommt man auf die "Werte" von x,y ?

Tue, 22 Sep 2015 08:41:18 +0000

Hallo,

so wie ich das verstanden habe gehst du von einer Art Nummerierung der Zeichen aus. j und k sind aber die Längen der Teilwörter, also eine Anzahl von Zeichen. Deshalb kannst du auch nur das kleinere vom größeren abziehen, sonst würde eine negative Anzahl an Zeichen herauskommen.

Oder habe ich das falsch verstanden?

Gruß

Marcel (Tutor)

Beantwortet: andere Zerlegung des Worts möglich ?

Tue, 22 Sep 2015 08:33:35 +0000

Hallo Herr Boehn,

ich bin mir nicht ganz sicher, ob ich Ihre Frage richtig verstanden habb: Also Sie wollen das Wort \( 0^n 1^n 0^n 1^n \) (so wie in der Lösung der Teilaufgabe b) wählen? Dann können Sie das PPL nur bei 0^n durchführen, da ja \( xy \leq n \) ist.

Habe ich Ihre Frage so richtig verstanden?

Viele Grüße

Friederike Pfeiffer-Bohnen und Lukas König

Beantwortet: allgemeine Fragen zum Pumping-Lemma

Tue, 22 Sep 2015 08:29:22 +0000

Hallo,

was hier sehr wichtig ist, und deshalb wiederhole ich es nochmal, obwohl es Jakob eigentlich schon gesagt hat, ist, dass man sich beim PPL nicht einfach Wörter konstanter Länge anschauen kann, denn diese kann man immer mit einem endlichen Automaten ohne Schleife erkennen. Habe ich ein Wort der Länge k, kann ich immer einen Automaten mit k+1 Zuständen bauen, der keine Schleife braucht und das Wort erkennt.

Anstelle einzelner Wörter betrachten wir beim PPL immer Wortklassen. Bspw. ist anbn nicht ein Wort, sondern abhängig von n eine beliebig große Menge von Wörtern. Jetzt können wir sagen, dass n von der Anzahl der Zustände des Automaten abhängt. Damit drehen wir den Spieß um, denn dann kann keiner sagen: Dann nehme ich halt einfach einen größeren Automaten. Wenn der Automat größer wird, wird eben auch das Wort länger. Die Grundidee des PPL ist dann, dass Wörter, die mindestens so lang sind wie die Anzahl der Zustände des Automaten, nur erkannt werden können, wenn der Automat eine Schleife hat. Und hat er eine Schleife, kann man diese beliebig oft durchlaufen, was einem "Pumpen" der Worts entspricht.

Viele Grüße

Lukas König