Theoretische und technische Informatik - ganz praktisch - Letzte Aktivität in PUM-AG

Kommentar bearbeitet: Unverständnis der Bemerkung in der Lösung

Fri, 06 Dec 2019 12:45:38 +0000

Hallo, bin eben auf die Frage gestoßen und habe mir das ganze mal angeschaut.
Leider treffe ich auf ähnliches Problem, wenn ich analog wie in Aufgabe 66 bis zu den drei Fällen vorgehe.
Erster Fall:
Die Anzahl der Nullen ist kleiner als die Anzahl der Zweien, somit wäre L'' nicht kontextfrei.
Zwar würde Fall zwei für L'' passen, Fall drei jedoch nicht. Müssen bei solch einer Fallunterscheidung alle Fälle der Sprache widersprechen?

Kann mir da jemand weiterhelfen?

Beantwortet: alternative Zerlegung PPL für kontextfrei Sprachen A66

Mon, 12 Feb 2018 19:39:37 +0000

Hallo,

deine Unterscheidungen im zweiten Fall überschneiden sich: wenn $vx$ eine $1$ oder eine $3$ enthält, kann es trotzdem auch eine $2$ enthalten.

Außerdem folgt im zweiten Fall für (1) nicht direkt, dass das gepumpte Wort nicht in der Sprache liegt: Mehr $0$en als $1$en sind grundsätzlich erlaubt, solange $\vert z\vert _0=\vert z \vert _2$ und $\vert z\vert _1=\vert z \vert _3$ gilt. Das gleiche gilt auch für die anderen Fälle.

Viele Grüße

Julia (Tutorin)

Beantwortet: Verständnis Hinweis

Sat, 10 Feb 2018 05:27:55 +0000

Hallo,

du hast Recht, dieser Fall ist auch bei L' nicht erfüllt, jedoch kannst du den Widerspruch der beiden anderen Fälle nicht zeigen, da auch s=t gelten könnte und somit Fall 1 und 3 für L' erfüllt wären.

Viele Grüße

Niklas (Tutor)

Beantwortet: Abkürzen der Beweisfälle

Tue, 17 Jan 2017 15:00:28 +0000

Natürlich, das ist ein ganz typisches Vorgehen. Man muss nur genau aufpassen, wie man formuliert, damit einem nicht Spezialfälle durch die Lappen gehen.

In dieser Aufgabe heißt es bspw. "$vx$ enthält keine $2$ und keine $3$", somit also nur die Zeichen $0$ und/oder $1$. Das ist absichtlich so negiert formuliert, denn positiv geschrieben müsste man schon mehr Fälle abdecken ($vx$ enthält entweder $0$ oder $1$ oder beides), was schnell fehleranfällig wird. Man braucht ein bisschen Übung, um zu sehen, wie man das geschickt macht - aber es ist auf jeden Fall eine legitime und gute Technik, die Sie einüben sollten.

Beantwortet: Verständnis

Tue, 02 Feb 2016 23:03:29 +0000

Hallo uodjt,

in dieser Aufgabe wurde als Wort z = uvwxy = 0^k 1^k 2^k 3^k gewählt.

Wenn du dir nun den ersten Fall anschaust, dann besteht vx aus s Nullen und t Einsen (vx = 0^s1^t). Demnach fehlen diese eben im Rest des Wortes uwy (d.h. von den k Nullen sind nur noch k-s Nullen übrig und von den k Einsen nur noch k-t Einsen). So erklären sich die Exponenten.

Zu deiner zweiten Frage: Nein, das wäre falsch, weil die Sprachdefinition über die Beziehung zwischen der Anzahl an Nullen und Dreien und die Beziehung zwischen der Anzahl an Einsen und Zweien keine Aussage macht. Laut der Sprachdefinition muss stattdessen die Anzahl der Nullen mit der Anzahl der Zweien übereinstimmen (gleicher Exponent i) und die Anzahl der Einsen mit der Anzahl der Dreien (gleicher Exponent j). Dagegen sagt die Aufgabe nichts darüber aus, dass die Exponenten i und j in einer besonderen Beziehung zueinander stehen müssen, daher kannst du über den Vergleich von Zahlen mit unterschiedlichem Exponenten (z.B. 1 und 2) auch keine Aussage zum Widerlegen des PPL treffen.

Ich hoffe, das hilft dir weiter!

Viele Grüße,

Janine (Tutorin)

Antwort bearbeitet: Vollständiger Beweis nötig oder reicht 1 Teilschritt?

Mon, 29 Dec 2014 10:25:47 +0000

Wie schon gesagt wurde, müssen alle Möglichkeiten durchgegangen werden.

Man kann das Pumping-Lemma übrigens auch als eine Art Spiel auffassen (man selbst spielt sozusagen "gegen das Pumping-Lemma"), wie es in einem Beitrag bei Stackexchange erklärt wird. Ich finde, das ist eine sehr schöne und intuitive Art, sich das Vorgehen klarzumachen, und vielleicht hilft es Ihnen auch beim Verständnis:

Here is an example for the pumping lemma: suppose the language $L=\{ a^k \mid k ∈ P\}$ is context free ($P$ is the set of prime numbers). The pumping lemma has a lot of $∃/∀$ quantifiers, so I will make this a bit like a game:

1. The pumping lemma gives you a $p$

2. You give a word $s$ of the language of length at least $p$

3. The pumping lemma rewrites it like this: $s=uvxyz$ with some conditions ($|vxy|≤p$ and $|vy|≥1$)

4. You give an integer $n≥0$

5. If $uv^nxy^nz$ is not in $L$, you win, $L$ is not context free.

For this particular language for $s$ any $a^k$ (with $k≥p$ and $k$ is

a prime number) will do the trick. Then the pumping lemma gives you

$uvxyz$ with $|vy|≥1$. To disprove the context-freeness, you need to

find $n$ such that $|uv^nxy^nz|$ is not a prime number.

$$|uv^nxy^nz|=|s|+(n-1)|vy|=k+(n-1)|vy|$$

And then $n=k+1$ will do: $k+k|vy|=k(1+|vy|)$ is not prime so $uv^nxy^nz\not\in L$. The pumping lemma can't be applied so $L$ is not context free.

Die Variable $p$ nennen wir normalerweise $n$, und die Pumpvariable, die hier $n$ genannt wurde, ist bei uns gewöhnlich $i$. Das Vorgehen funktioniert analog auch beim Pumping-Lemma für reguläre Sprachen.

Vergleichen Sie hierzu auch den Beweis, dass die obige Sprache $L$ nicht regulär ist aus Aufgabe HU-1-4.

Beantwortet: Verständnisschwierigkeit: Folgerung von vx zu z' ?

Tue, 25 Nov 2014 08:48:03 +0000

Hallo David,

V und x müssen laut Vorraussetzung (2) existieren. Im ersten Beispiel sind $vx = 0^s1^t$. Wenn man jetzt mit i = 0 pumpt, dann bedeutet das, dass s nullen und t einsen im wort uwy fehlen. Dann kommst du genau auf dein z.

Ich hoffe, dass ich dir damit etwas helfen konnte.

Grüße,

Jördis (Tutorin)

Kommentiert: alternative argumentation

Tue, 25 Nov 2014 08:45:33 +0000

Hallo,

genau, darum geht es ja beim PPL.

s. Bedingung c) für alle i aus No : $u(v^i)w(x^i)y € L$

Somit muss, damit die Sprache nicht kontextfrei ist, dein Wort in jeder Zerlegung mindestens eine Pumpvariable i besitzten, für das das resultierende Wort nicht mehr in der Sprache liegt.

Viele Grüße

Philippe