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

Beantwortet: Mit einem bestimmten Gegenbeispiel nicht kontextfreie Sprache zu zeigen

Mon, 20 Jan 2020 08:47:24 +0000

Hallo,

ein Gegenbeispiel reicht nicht aus. Man muss für alle möglichen Zerlegungen $w=uvzxy$ ein $i$ finden, so dass $uv^izx^iy \notin L$.

Viele Grüße,
Julia (Tutorin)

Beantwortet: Warum werden -1/-2 abgezogen

Sun, 20 Jan 2019 12:01:21 +0000

Hallo uyuee,

wir haben z = anbn+1cn+2 als Wort gewählt. Mit der Beziehung |uviwxiy|a > |uviwxiy|c − 2 zeigen wir, dass es in das aufgepummtes Wort nicht zwei c's mehr gibt als a's und somit, dass uviwxiy nicht in L liegt.

Viele Grüße,

Natalie (Tutorin)

Beantwortet: Alternativlösung

Mon, 16 Jan 2017 18:35:03 +0000

Hallo,

theoretisch kannst du auch deinen Ansatz mit z= a^nb^2nc^3n verwenden, jedoch stimmt deine Argumentation unten nicht.
a^(n-m)b^2nc^3n ist doch noch Teil der Sprache. Es sind weniger a als b und c und weniger b als c.

Du darfst hier eben nicht mit 0 pumpen, sondern z.B. mit i>n, damit du mehr a als b hast.

Grüße, Sören (Tutor)

Bonusklausur 2013

Thu, 12 Jan 2017 11:20:19 +0000

Hallo,

ich habe ein Frage: Ich habe folgenden Kellerauromaten geschrieben(s.u):

Wieso akezptier der KA das Beispielwort nicht? Er müsste doch wenn er das letzte a gelesen hat, als nachdem er (s3, a, k) => (s3,k) ausgeführt hat, als letztes den Übergang (s3, lamda, k) => (se, k) ausführen und stehen bleiben und das Wort akzeptieren.

hier c = #

pda:
(s0, a, k) => (s1, ak);
(s1, b,a) => (s1, ba);
(s1, a,a) =>(s1, aa);
(s1, a,b) =>(s1, ab);
(s1, c,a) => (s2, a);
(s2, a,a) => (s2, lambda);
(s2, a,b) => (s2, b);
(s2, b,b) => (s2,lambda);
(s2, a,k) => (s3, k);
(s3, a,k) => (s3, k);
(s3, lamda,k) => (se, k)

--declarations--
s0=s0;
F=se;
kSymb=k;
inputs=aabaacaaabaaaa
--declarations-end--

Vielen Dank!

Beantwortet: Unterscheidung i=0 und i=2

Mon, 18 Jan 2016 23:24:46 +0000

Hallo ukdxs,

in der vorherigen Frage war die FRage, ob allgemein immer i=10 getestet werden koenne. Wie damals beantwortet muss man sich eine geschickte Pumpvariable waehlen und dazu ist weder i=0 noch i=1 gut geeignet. $ i=2$ oder groesser, eignet sich meist besser, da schnell eine der zwingenden Belegungne widerlegt werden kann. Auf jeden Fall haengt es von der konkreten Sprache ab.

Viel Erfolg,

Marvin (Tutor)

Beantwortet: wie hoch darf man pumpen

Sun, 17 Jan 2016 17:15:52 +0000

Sie dürfen auch $i$ abhängig von den im PPL vorkommenden Variablen wählen, denn die dritte Bedingung sagt ja, dass es für alle $i$ gelten muss (also reicht es, ein einziges $i$ zu finden, für das es nicht gilt).

$i=n, 2n, 3n, n^2$ usw. wäre also zulässig. Allerdings weiß ich nicht, wie Sie das in diesem Fall ausnützen wollen - vielleicht erklären Sie das nochmal genauer? Bei dieser Aufgabe brauchen Sie das im Prinzip nicht, weil $i=0$ bzw. $i=2$ je nach Fall ausreicht (siehe Lösung).

Beantwortet: Beispiel + Lösung: so korrekt?

Fri, 25 Sep 2015 16:21:45 +0000

Hallo,

naja, im Prinzip geht es in die richtige Richtung. Aber auf jeden Fall fehlt hier die Unterscheidung zwischen i=0 und i=2. Sie können nicht immer mit dem gleichen i pumpen, sondern müssen es anpassen, je nachdem, welche Verteilung sie vorfinden.

Viele Grüße

Lukas König

Beantwortet: verkürzen des Lösungswegs?

Fri, 25 Sep 2015 16:20:49 +0000

Hallo,

das hängt sehr davon ab, was genau Sie schreiben würden. Ich sehe ein, dass es gewisse Symmetrie-Eigenschaften der verschiedenen Fälle gibt, aber es ist wichtig, dass wirklich alle Möglichkeiten abgedeckt werden. Wenn Sie schreiben "kurz" und "erwähnen", dann bin ich nicht sicher, ob Sie das in Ihrer Vorstellung wirklich hinkriegen würden. Das heißt aber nicht, dass es nicht kürzer geht als in der Musterlösung.

Vielleicht können Sie ja mal einen konkreten Vorschlag posten (also einen wirklichen Text, wie Sie ihn in der Bonusklausur schreiben würden)?

Viele Grüße

Lukas König

Beantwortet: alternative Lösung möglich?

Fri, 25 Sep 2015 16:19:09 +0000

Allgemein zu Pumpinglemma-Aufgaben:

- n muss variabel sein ( $ " n \in N " $ ), man darf also kein Wort mit einer fixen Länge wählen.

- Der Widerspruch muss für alle möglichen Partionen gezeigt werden, nicht nur eine

Ich vermute, dass es bei deinem Beweis zumindest der zweiten Punkt problematisch ist.

Um deinen Beweis konkret beurteilen zu können: Kannst du dein Wort + kurze Erklärung, warum x und v in den b's liegen muss, posten? Vielleicht hilft dir auch dieser Thread, in dem schon einige prinzipielle Fragen geklärt wurden:

HU-1-4

Tobias (Tutor)