Theoretische und technische Informatik - ganz praktisch
Herzlich willkommen auf der Question/Answer-Plattform zu Grundlagen der Informatik II. Wir wünschen Ihnen viel Spaß beim Lernen und Diskutieren!
Loggen Sie sich mit Ihrem KIT-Account (u...) ein, um loszulegen!
Beachten Sie auch diese Informationen zum Schnelleinstieg.
(Nicht-KIT-Studierende beachten bitte diese Informationen.)

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

–1 Punkt
169 Aufrufe

Hallo,

muss man wie in der Lösung alle verschiedenen Mgk testen so wie in der Lösung oder würde es auch reichen, einen der drei Beweispunkte vx = a^sb^t..... zu führen. 

a,b € {0,1,2,3}

Gruß

 

Gefragt 25, Nov 2014 in PUM-AG von uafjv uafjv Tutor(in) (167,990 Punkte)  

2 Antworten

–1 Punkt
 
Beste Antwort

Hallo,

nach dem PPL muss ja nur eine solche Zerlegung existieren, damit L kontextfrei ist. Im Umkehrschluss heißt das, dass alle Zerlegungen deines Wortes für den Beweis, dass L nicht kontextfrei ist, zu einem Widerspruch führen müssen.

Würdest du also nur einen der Beweispunkte durchführen, wäre der Beweis unvollständig, da eine der anderen Möglichkeiten evtl. nicht zu einem Widerspruch führt. Deshalb müssen alle gezeigt werden.

Viele Grüße

Philippe (Tutor)

 

Beantwortet 25, Nov 2014 von uafjv uafjv Tutor(in) (167,990 Punkte)  
Wäre dann aber die Aufgeführte Lösung auch nicht ganz komplett?? Denn es fehlen die Fälle, wo vxy nur aus 0, 1, 2 oder 3 besteht. Da müsste man doch auch einen formalen Widerspruch liefern...

Wäre es nicth bei solchen Aufgaben sinnvoll, wie bei den anderen PL zu kontextfreien Sprachen, mit Text zu argumentieren, sodass man nicth der Gefahr entgegenläuft, einen möglichen Fall zu bersehen??

lg
Nein, das ist darin enthalten, dass s und t aus N inklusive 0 sind. Es gilt lediglich, dass s+t > 0 sein muss.

Ich denke, das ist geschmackssache. Wenn man allerdings rein textuell argumentiert, besteht die Gefahr, dass man die Begründung nur unzureichend ausführt. Dafür ist die Erklärung für die meisten aber wahrscheinlich intuitiver.

Viele Grüße

Philippe (Tutor)
+1 Punkt
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 28, Dez 2014 von Lukas König Dozent (10,065,100 Punkte)  
Bearbeitet 29, Dez 2014 von Lukas König
...