Theoretische und technische Informatik - ganz praktisch - Letzte Fragen & Antworten in HU-1-4

Beantwortet: alternativ PPL

Fri, 21 Jan 2022 17:02:10 +0000

Hallo uqyxt,

dein Wort hier wäre 0^2n1, das gehört nicht zur Sprache, da es kein Palindrom ist. Wenn du z als 0^2n-j10^2n schreibst, dann passt das mit i=0.

Viele Grüße

Anne (Tutorin)

Beantwortet: Pumping Lemma L4

Sat, 17 Nov 2018 21:40:16 +0000

Hallo,

ja. Deiner Vorschlag ist auch richtig.

Viele Grüße,
Runxi (Tutorin)

Beantwortet: PPL - andere Lösung möglich? Darf man k=1 wählen zum beweisen?

Fri, 12 Jan 2018 13:34:25 +0000

Hallo,

Zu deiner Vorgehensweise wurde schon eine ähnliche Frage gepostet:

http://info2.aifb.kit.edu/qa/index.php?qa=2150&qa_1=a-anderes-vorgehen-bei-beweis-erlaubt&show=2151#a2151

Das sollte dir weiterhelfen. Ansonsten gerne nochmal melden.

Viele Grüße,

Timon (Tutor)

Beantwortet: Frage zu dieser Aufgabe

Mon, 16 Jan 2017 09:27:38 +0000

Hallo,

wenn du von w'=a^(n^2-j) ausgehst, dann musst du quasi zeigen, dass n^2-j keine Quadratzahl ist.
Die nächst kleinere Quadratzahl wäre ja (n−1)^2=n^2−2n+1.
daher müsste gelten j= 2n-1 und da j =< n sein muss, ist das für hinreichend große j (größer 1) nicht gegeben und demnach ist das Wort nicht Teil der Sprache.

Grüße, Sören

Beantwortet: Übungsblatt 1 Aufgabe 4a)

Mon, 25 Jan 2016 16:30:07 +0000

Hallo,

das Problem bei deiner Lösung ist, dass man dann nichtmehr nur auf den Endzustand kommt wenn 3 Einsen direkt nach einander kommen würden, sondern sobald irgendwann 3 Einsen eingelesen wurden.
In der Lösung wenn man 111 einliest kommt man in einen Zustand in dem man nicht mehr herauskommt und der kein Endzustand ist.
Wäre man wie du vorgeschlagen hast in s2 und liest eine 0, der Pfeil zeigt auf s2, dann wäre man sobald eine 1 kommt anschließend in s3 und das Wort würde nicht mehr akzeptiert werden, obwohl keine Regel verletzt wurde.

In anderen Worten de Automat den du vorgeschlagen hast, würde alle Wörter akzeptieren die maximal 2 Einsen haben, egal in welcher Reihenfolge und ob die direkt nach einander kommen. Der Automat hier soll aber nur nicht akzeptieren wenn drei Einsen direkt nach einander geschrieben wurden.

Ich hoffe das hilft.

Viele Grüße,

Marc (Tutor)

Beantwortet: a) verständnisproblem

Mon, 16 Nov 2015 12:20:03 +0000

Hallo,

da ich mir nicht sicher war, welchen Schritt der Aufgabe du meintest, habe ich mal die gesamte Lösung kommentiert. Alles in schwarzer Schrift ist aus der Musterlösung abgeschrieben, alles in anderen Farben sind meine Erläuterungen dazu. Ich hoffe, dass dir das weiterhilft.

Viele Grüße

Sandra (Tutor)

Beantwortet: b): Verständnisproblem bzgl. Betrachtung der Partitionen

Thu, 17 Sep 2015 14:31:08 +0000

Hallo,

was Marc und Paul schreiben ist so nicht ganz korrekt. Im Pumpinglemma heißt es "es gibt eine Partition", nicht "für alle beliebigen Partitionen". Daher muss man im Umkehrschluss, wie Sie richtig geschrieben haben(!), alle möglichen Partitionen betrachten. Wenn wir in der Musterlösung schreiben "Betrachte eine beliebige Partition", dann ist genau das gemeint. Wenn wir eine beliebige Partition betrachten, heißt das, dass wir keine Einschränkungen für x, y, z vornehmen, also untersuchen wir alle Möglichkeiten.

Viele Grüße

Lukas König

Beantwortet: c): Anderer Ansatz

Thu, 17 Sep 2015 14:20:09 +0000

Hallo,

der Gedankengang ist nachvollziehbar. Allerdings ist das Problem bei diesem Beweis, dass deine Behauptung nicht vollständig bewiesen wird und das zu beweisen ist natürlich nicht trivial, wie du schon selbst gesagst hast.

Viele Grüße,

Sebastian (Tutor)

Beantwortet: a): Verständnisproblem bei Musterlösung

Thu, 17 Sep 2015 14:15:39 +0000

Hallo,

da hast du sicherlich recht. Genauer müsste es heißen, dass \( i_x + i_y \leq n \). Dann ist Bedingung (1) erfüllt.

Gruß,

Marius (Tutor)

Beantwortet: a): Wird bei |xy|=2n nicht die obere Bed. verletzt?

Thu, 17 Sep 2015 14:07:04 +0000

Hallo,

Es ist richtig dass \( |xy| \leq n \) definiert wurde, die zweite Annahme die du triffst ist allerings nicht ganz richtig. \( (i_y) \) ist definiert zwischen 1 und n daraus folgt dass \( (ix) \) definiert ist zwischen 0 und (n-1).

Dies folgt aus der 1. Bedinung (\( \mid xy \mid \leq n \)) die gleichzeitig auch noch für die Folgende "Regel" sorgt:

\( (i_x) \) und \( (i_y) \) sind zusammen niemals größer als n, somit kann die obere Bedingung, da sie hier ja direkt Einfluss nimmt nicht verletzt werden.

Ich hoffe ich konnte dir helfen, falls es noch weitere Fragen gibt, frage ruhig. :)

Viele Grüße

Marc (Tutor)

Beantwortet: c): Kann man z.B. i=2 wählen?

Thu, 17 Sep 2015 14:00:58 +0000

Hallo Robin,

wenn du i=2 wählst kannst du keine Aussage darüber treffen, ob die so entstehende Wortlänge eine Primzahl ist oder nicht, da die Länge von z.B. x frei zischen 1 und n gewählt werden kann.

Ein Beispiel wäre für n = 3, w = 11111 (5 Einser)

Man wähle \( x = 1, y = 11, z = 11 (|xy| = 3 \leq n; |y| = 1 \leq 1) \)

Für xyyz (also i=2) entsteht somit das Wort 1111111 (7 Einser). Da 7 auch eine Primzahl ist, ist das so entstehende Wort auch Teil der Sprache.

Beantwortet: c): alternativer Lösungsvorschlag

Thu, 17 Sep 2015 13:57:37 +0000

Ich habe übrigens als Antwort auf einen Beitrag im Aufgabenpool-Forum einen sehr schönen Beweis gepostet (nicht von mir, deshalb ist das kein Selbstlob :-)), dass die Sprache der Primzahlen auch nicht kontextfrei ist.

Dort wird das PPL als eine Art Spiel aufgefasst, was ich sehr interessant finde (geht genauso beim PPL für reguläre Sprachen). Vielleicht hilft es Ihnen ja beim Verständnis.

Viele Grüße

Lukas König

Beantwortet: 2. Schritt bei Reduzierung des EA

Thu, 17 Sep 2015 13:55:15 +0000

Hallo,

um auf die Felder zu kommen, die in der Tabelle mit x1 markiert werdne müssen, musst du Schritt 2 des Algorithmus aus der Vorlesung anwenden. Den Algorithmus findest du auf Folie 38 des zweiten Foliensatzes, danach kommt dann die Anwendung mit einem Beispiel.

Als erstes trägst du die x0 in die dreieckige Tabelle ein, danach folgen die x1, x2 etc. Nun zu deiner Frage, wie kommt man zu den x1: Du betrachtest jedes noch leere Feld der dreieckigen Tabelle und merkst dir die dazu passenden Zustandskombinationen. Diese prüfst du dann in der Tabelle mit den Zustandsübergängen (die rechteckige Tabelle daneben). Durch Prüfen der verschiedenen möglichen Eingaben erhältst du ein "neues" paar Zustände, dieses prüfst du wieder in der dreieckigen Tabelle. Gelangst du nun auf einen schon markierten Zustand (bei Schritt 2 also auf einen Eintrag, in dem x0 steht) markierst du das Feld welches du am Anfang prüfen wolltest mit x1.

Am Beispiel der Vorlesung (Folie 42, zweiter Vorlesungssatz) erklärt: Wir betrachten die Zustandskombination s0/s1 der dreieckigen Tabelle. In dieser Zelle steht am Anfang nichts. Wir prüfen also die Zustände so/s1 in der Zustandsübergangstabelle. Wir gelangen durch Eingabe einer 0 in die Zustandskombination s1/s4 und durch Eingabe einer 1 in die Kombination s2/s5. Sobald eine der Kombinationen schon in der dreieckigen Tabelle markiert wurde, sind wir fertig und markieren die ursprüngliche Kombination. In diesem Beispiel sind es sogar beide Kombinationen: s1/s4 und s2/s5 sind in der Tabelle schon mit s0 markiert -> wir markieren s0/s1 mit s1.

Ich hoffe ich konnte dir weiterhelfen.

Viele Grüße

Felix (Tutor)

Beantwortet: c): Was ist die Idee des Ansatzes?

Thu, 17 Sep 2015 13:44:27 +0000

Warum i = |xy| ?

Ich kann dir leider kein allgemeingültiges Kochrezept angeben, mit dem man bei Pumpinglemma-Aufgaben stets und schnell ein geeignetes i finden kann. Teils funktioniert blindes Ausprobieren von i = 0 oder i = 2, aber meist ist eine Idee, wie man zu dem Widerspruch kommt (hier: keine Primzahl lässt sich als Produkt von zwei natürlichen Zahlen > 1 darstellen -> Länge des gepumpten Wortes als Produkt darstellen) nötig. Dann wählt man i entsprechend. Evtl. muss man auch erst mal verschiedene Ansätze und i ausprobieren, da man nicht jeden Zwischenschritt vollständig überblickt... Insofern wählt man i = |xy|, weil dann so umformen kann, dass man zum Ziel (Widerspruch) kommt.

Zu deiner zweiten Frage:

\( i= |xy| = |x| + |y| = i_x +i_y \) und \( y = 1^{i_y} \) einsetzen:
\( y^i = (1^{i_y})^i = (1^{i_y})^{i_x + i_y} \)
Mit den Potenzgesetzen \( (a^b)^c = a^{b*c} \) kommt man auf \(1^{i_y*(i_x + i_y)} \)

Ich hoffe, zumindest deine zweite Frage beantwortet zu haben.

Tobias (Tutor)

EDIT:

Sorry, hab mich vertippt, es muss naturlich \( i = |xz| = |x| + |z| = i_x +i_z \) und \( y^i = ... = (1^{i_y})^{i_x+i_z} \) heißen!

Beantwortet: a): Widerspruchsbeweis möglich?

Thu, 17 Sep 2015 13:39:15 +0000

Nein, das geht aus 2 Gründen nicht:

1. Für dein Wort ("aaaa") gilt die Bedingung \( |w| \leq n \) nur für \( n \leq 4 \). Wie bereits oben vom den Übungsleitern und mir erklärt, kann das n/die Anzahl Zustände des EA aber beliebig groß sein und darf im Beweis nicht auf einen festen Wert gesetzt werden.

2. Das Pumpinglemma sagt nur aus, dass (mindestens) eine Aufteilung xyz existiert, bei der man das y pumpen kann. Das heißt nicht, dass man bei jeder Aufteilung das y pumpen kann und das entstandene Wort noch in der Sprache ist. Du musst also für den Widerspruch zeigen, dass keine solche Aufteilung existiert. Eine einzelne Aufteilung heraus zu greifen, reicht nicht aus, da es eine andere Aufteilung geben kann, mit der das Pumpinglemma erfüllt ist.

Grüße,

Tobias (Tutor)

Beantwortet: b): Ist die Zerlegung in x,y,z beliebig ?

Thu, 17 Sep 2015 13:18:46 +0000

Hallo,

ja der von dir durchgeführte Beweis ist möglich.

Zur allgemeinen Frage:

Beim PPL reicht es zu zeigen, dass es ein Wort \( w \in L\) mit \( \mid w \mid \leq n \) gibt, sodass für alle Zerlegungen w=xyz mindestens eine der drei Forderungen nicht gilt. Grundsätzlich ist kann die Zerlegung frei gewählt werden.

Viele Grüße,

Sebastian (Tutor)

Beantwortet: Kann man in der Klausur anhand eines konkreten Zahlenbeispiels beweisen?

Thu, 17 Sep 2015 13:05:25 +0000

Nein, das ist nicht möglich. Sie müssen über alle möglichen endlichen Automaten (bzw. Grammatiken) argumentieren, und ein endlicher Automat hat zwar nur endlich viele Zustände, aber eben beliebig viele. Wenn Sie n=5 setzen, argumentieren Sie nur über Automaten mit maximal 5 Zuständen, was nicht der Fragestellung entspricht.

Viele Grüße

Lukas König und Friederike Pfeiffer-Bohnen

Beantwortet: c): Ausführlichere Erklärung?

Thu, 17 Sep 2015 13:02:19 +0000

Hallo,

wenn du dir unten die Zerlegung anschaust, dann siehst du, dass gelten muss, dass der Wert in beiden Klammen größer oder gleich 2 ist.

Wäre dies nicht der Fall, dann könnte in einer Klammer 1 stehen und bekanntlich ist 1*x = x. Das wiederum würde aber nicht zum geforderten Ergebnis führen, dass eine Primzahl als Resultat der Multiplikation ausgeschlossen ist, denn auch hier gilt wieder Primzahl multipliziert mit eins ergibt Primzahl.

Gilt allerdings >= zwei für beide Faktoren, so lässt sich die resultierende Zahl durch zwei (oder mehr) Teilen, ist also keine Primzahl. Dadurch, dass du weißt, dass \( |y| \leq |xy| \leq n \) ist, musst du \( |w| \leq n + 2 \) wählen, damit das Wort mit weggelassenem y (also xz) noch mindestens 2 lang ist.

Ich hoffe, das war verständlich ;)

Viele Grüße

Philippe (Tutor)

Beantwortet: Verständnis zur k-Äquivalenz

Thu, 17 Sep 2015 12:59:22 +0000

Hallo,

zunächst geht es eigentlich nur um einen Automaten. Der reduzierte Automat A' fasst dann lediglich die im Automaten A äquivalenten (also k = unendlich) Zustände zusammen.

Das Ganze funktioniert immer rekursiv. Das heißt, du startest bei k = 0. Hier geht es darum, dass zwei Zustände 0-äquivalent sind, wenn sie entweder beide Endzustände sind, oder wenn sie beide Nicht-Endzustände sind.

Alles weitere lässt sich hierauf zurückführen.

Bsp: Von Zustand 1 gelange ich durch Eingabe 0 auf Zustand 1a und durch Eingabe 1 auf Zustand 1b.

Von Zustand 2 gelange ich durch Eingabe 0 auf Zustand 2a und durch Eingabe 1 auf Zustand 2b.

Die Eingabe hat die Länge eins. Wenn jetzt sowohl 1a und 2a 0-äquivalent sind, als auch 1b und 2b (es muss aber nicht "über kreuz" funktionieren), dann sind Zustand 1 und 2 1-äquivalent (du konntest, ausgehend von Zustand 1 und 2 einen Schritt gehen, ohne die 0-äquivalenz zu verlieren).

In dieser Weise erweiterst du dein Wort. Wenn sich an der k-äquivalenz nichts mehr ändert, dann weißt du von allen, die auf der höchsten Stufe sind, dass sie eben auch äquivalent sind.

Also kommst du mit diesen Zuständen, unabhängig von der Eingabe, auf das gleiche Ergebnis - sie sind somit redundant und können ausgelassen werden.

Ich hoffe, ich konnte dir ein wenig weiterhelfen.

Viele Grüße

Philippe (Tutor)

Beantwortet: Wie kommt man auf die Zerlegung mit i ?

Thu, 17 Sep 2015 12:54:55 +0000

Bei der Zerlegung wird das Wort nicht in drei gleichlange Teile geteilt. Es muss nur so aufgeteilt werden, dass eben \( |xy| \leq n \) ist (plus die anderen Bedingungen).

Das liegt daran, dass aufgrund der Eigenschaften endlicher Automaten (s. Vorlesung), bei einem Wort, dass mindestens soviele Zeichen hat wie es Zustände gibt (n), in den ersten n Zeichen eine Schleife durchlaufen wird. Diese Schleife kann man beliebig oft durchlaufen, da man immer wieder am Start der Schleife rauskommt. Von dort aus hat man dann immer die selben Alternativen. Eben das wird durch das i repräsentiert, das beliebig oft wiederholt werden kann.

Ich hoffe, ich konnte euch weiterhelfen.

Viele Grüße

Philippe

Beantwortet: a): Anderes Vorgehen bei Beweis erlaubt?

Thu, 17 Sep 2015 12:49:52 +0000

Hallo zusammen,

Das funktioniert m.E. auch, im Prinzip machst du das Gleiche wie in der Lösung nur mit i=0 statt i=2. Eines der beiden zu zeigen ist ausreichend.

Allerdings musst du begründen, warum \( w'=xz=a^{{n^2}-j} \) nicht aus der Sprache ist. Das wiederum liegt daran, dass \( (n-1)^{2} = n^{2} - 2n + 1 \).

Da der Exponent von z wegen \( j \leq n \) nur im Fall n=1 den gleichen Wert annimmt, ist das Wort nicht Teil der Sprache.

Ich hoffe, ich konnte euch weiterhelfen.

Viele Grüße

Philippe