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 pumpinglemma turingmaschine tipp zahlendarstellung cmos klausurrelevant bonusklausur 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 cocke-younger-kasami-algorithmus kontextsensitive-grammatik kontextfreie-grammatik fehlererkennbarkeit huffman-kodierung hauptklausur vorlesungsfolien kontextfreie-sprache polynomialzeitreduktion faq gleitkommazahl fehlerkorrigierbarkeit rechtslineare-grammatik dateiorganisation cache darstellung-klausur nachklausur xwizard adressierungsarten lambda mealy endliche-automaten konjunktive-normalform pipelining zustände saalübung leeres-wort ohne-lösungen betriebssystem speicherorganisation moore monotone-grammatik 2-komplement fehler reguläre-sprache hammingzahl monoton lösungsweg pumping-lemma-für-kontextfreie-sprachen kodierung berechenbarkeit pumping-lemma klausureinsicht disjunktive-normalform info-ii bussysteme rechnerarchitektur abzählbarkeit komplexitätsklassen ableitungsbaum vorlesungsaufzeichnung round-robin entscheidbarkeit minimierung-endlicher-automaten chomsky-klassen von-neumann-rechner binärzahl entscheidbar programmiersprachen aufzählbarkeit stern-symbol automaten schaltnetze-und-schaltwerke nukit-fragen bewertung zugriffsarten umformung adressierung mengen binär-subtrahieren

Kategorien

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