Theoretische und technische Informatik - ganz praktisch - Letzte Fragen & Antworten in PUM-AG

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)

Beantwortet: Unverständnis der Bemerkung in der Lösung

Mon, 12 Jan 2015 17:40:34 +0000

Hallo Maximilian,

Die beiden Sprachen L' und L'' kannst du dir schön im Kellerautomaten vorstellen, damit wird auch klar wieso diese beiden kontextfrei sind.

Bei L={0$^i$1$^i$2$^j$3$^j$ | i,j $\in$ $\mathbb{N}$} legt der Kellerautomat zuerst die 0 in den Keller, prüft anschließend ob es genau so viele 1 gibt, anschließend sollte der Keller leer sein, danach überprüft er das selbe mit 2 und 3.

Bei L''={0$^i$1$^j$2$^j$3$^i$ | i,j $\in$ \mathbb{N}}legt der Kellerautomat alle 0er ab, danach alle 1er, prüft ob es gleich viele 2er wie 1er gibt und anschließend prüft er ob es gleich viele 3er wie 0er gibt. Nach dem LiFo Prinzip, ist es relativ anschaulich wie ein Kellerautomat so etwas akzeptieren könnte.

Ich hoffe ich konnte dir helfen, falls du noch weitere Fragen hast stelle sie gerne :)

Viele Grüße,

Marc (Tutor)

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

Sun, 28 Dec 2014 22:44:41 +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)

Beantwortet: alternative argumentation

Tue, 25 Nov 2014 08:44:12 +0000

Hallo,

prinzipiell passt das schon so, allerdings würde mir persönlich bei der Begründung noch der entscheidende Punkt fehlen, nämlich dass vwx aufgrund eben dessen, dass es maximal zwei versch. Zeichen enthält, nie in zwei Zahlenbereiche mit dem gleichen Index reinreichen kann, und somit nur ein i, oder i und j, oder ein j, aber nie beide is oder beide js gleichzeitig gepumpt werden können (mit i meine ich in diesem Kontext das i aus der Sprachen-Definition).

Ansonsten ist es prinzipiell genau das, was in der Lösung mathematisch formuliert wurde, in textform.

Viele Grüße

Philippe (Tutor)