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.)

Beliebteste Tags

verständnis alternativlösung klausur kellerautomat endlicher-automat grammatik regulärer-ausdruck turingmaschine pumpinglemma tipp zahlendarstellung cmos bonusklausur klausurrelevant komplexität schaltwerk binary-decision-diagram deterministisch assembler schaltnetz minimierung sprachen nichtdeterministisch huffman chomsky-normalform fehler-in-aufgabe anwesenheitsübung rechtslinear heimübung flip-flop huffman-kodierung cocke-younger-kasami-algorithmus kontextsensitive-grammatik kontextfreie-grammatik fehlererkennbarkeit hauptklausur vorlesungsfolien polynomialzeitreduktion kontextfreie-sprache faq gleitkommazahl fehlerkorrigierbarkeit rechtslineare-grammatik dateiorganisation cache darstellung-klausur nachklausur xwizard adressierungsarten mealy lambda endliche-automaten konjunktive-normalform pipelining zustände saalübung leeres-wort moore ohne-lösungen betriebssystem speicherorganisation monotone-grammatik 2-komplement hammingzahl lösungsweg fehler pumping-lemma-für-kontextfreie-sprachen pumping-lemma reguläre-sprache monoton kodierung berechenbarkeit klausureinsicht disjunktive-normalform abzählbarkeit info-ii bussysteme rechnerarchitektur entscheidbarkeit komplexitätsklassen chomsky-klassen ableitungsbaum vorlesungsaufzeichnung round-robin aufzählbarkeit minimierung-endlicher-automaten von-neumann-rechner binärzahl entscheidbar programmiersprachen stern-symbol automaten schaltnetze-und-schaltwerke nukit-fragen bewertung zugriffsarten umformung adressierung mengen binär-subtrahieren

Kategorien

0 Pluspunkte 1 Minuspunkt
358 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ß

 

in PUM-AG von uafjv uafjv Tutor(in) (168k Punkte)  

2 Antworten

0 Pluspunkte 1 Minuspunkt
 
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)

 

von uafjv uafjv Tutor(in) (168k Punkte)  
0 0
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
0 0
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 Pluspunkt 0 Minuspunkte
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
von Dozent (10.1m Punkte)  
Bearbeitet von
...