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 sprachen minimierung nichtdeterministisch huffman fehler-in-aufgabe chomsky-normalform anwesenheitsübung rechtslinear heimübung flip-flop cocke-younger-kasami-algorithmus kontextsensitive-grammatik kontextfreie-grammatik huffman-kodierung hauptklausur fehlererkennbarkeit vorlesungsfolien kontextfreie-sprache polynomialzeitreduktion faq gleitkommazahl fehlerkorrigierbarkeit rechtslineare-grammatik dateiorganisation cache darstellung-klausur nachklausur xwizard adressierungsarten lambda mealy konjunktive-normalform pipelining zustände saalübung leeres-wort endliche-automaten 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 klausureinsicht disjunktive-normalform pumping-lemma info-ii bussysteme rechnerarchitektur abzählbarkeit komplexitätsklassen ableitungsbaum vorlesungsaufzeichnung round-robin minimierung-endlicher-automaten chomsky-klassen binärzahl entscheidbar programmiersprachen entscheidbarkeit aufzählbarkeit stern-symbol automaten nukit-fragen bewertung zugriffsarten von-neumann-rechner umformung adressierung mengen binär-subtrahieren organsiation

Kategorien

0 Pluspunkte 0 Minuspunkte
162 Aufrufe

Ich versuche gerade die Lösung nachzuvollziehen, komme aber nicht weiter. Wenn x=lambda, |y| = 1, |z| = |w| -1 gilt, dann kann y doch nur a oder b sein und nicht wie in der Lösung beschrieben a, b oder c. 

Ich habe das PPL selbst versucht zu beweisen, ist das so korrekt?

 

in HU-3-4 von uodsh uodsh Eins-Komma-Null-Anwärter(in) (2.3k Punkte)  

2 Antworten

0 Pluspunkte 0 Minuspunkte
 
Beste Antwort
Hallo!

Zu deiner ersten Frage: Der zweite Teil der Vereinigung in der Lösung ist die Sprache b^m c^n. b,n>=0. Wenn das Wort also aus dieser Sprache L´´ kommt und m 0 ist ist y ein c.

Zu deinem Beweis: Du zeigst das PL nur für die Sprache L´. Außerdem wird der Weg den du benutzt meistens benutzt um zu zeiden, dass das Pumping Lemma nicht gilt. Als Tipp kann ich dir mitgeben, dass du dir eher eine logische Erklärung suchst, um zu zeigen, dass das PL gilt und diese dann auszuformulieren.

Felix(Tutor)

 

PS: Die Lösung nochmal kurz erklärt: wir wollen ja zeigen, dass es für jedes wort EINE Zerlegung gibt, in der man y pumpen kann. In beiden Sprachen L´ und L´´ kann man den ersten Buchstaben immer pumpen. Wie in der Lösung beschrieben, zerlegt man das Wort also so, dass y nur der erste Buchstabe ist und kann dann y pumpen. Also gilt das PL.
von uwdtl uwdtl Tutor(in) (103k Punkte)  
ausgewählt von uodsh uodsh
0 Pluspunkte 0 Minuspunkte

Ich bin nicht sicher, was Sie hier versuchen, denn Sie beziehen sich ja nur auf einen Teil der Sprache $L_1$. Wichtig ist zu verstehen, dass wir hier ausnahmsweise andersherum vorgehen als sonst - wir wollen diesmal wirklich eine Zerlegung finden, sodass die Eigenschaften (1), (2) und (3) gelten. Und nicht - wie normalerweise - zeigen, dass es keine Zerlegung gibt, für die diese Eigenschaften gelten.

In Ihrer Argumentation schreiben Sie, $xy$ könne nur zwei der drei Buchstaben enthalten - dabei sind Sie aber auf der klassischen Schiene mit dem Widerspruchsbeweis. Stattdessen können wir es uns diesmal leicht machen und tatsächlich eine Zerlegung auswählen. Es reicht uns, eine zu finden, wir müssen nicht über alle argumentieren.

Und diese eine legen wir einfach fest durch

  • $x=\lambda$,
  • $|y| = 1$,
  • $z$ = der ganze Rest des Wortes $w$.

$y$ ist also gerade das erste Zeichen des Wortes $w$. Offenbar sind die drei Eigenschaften so erfüllt. Und nun kann es immer noch zwei Fälle geben: Entweder ist $y=a$ oder $y \neq a$. Ist $y=a$, gilt $$w=a^\star b^nc^n \in L_1$$ Pumpen wir nun zu $xy^iz$, verändern wir nur die Anzahl an $a$'s, also bleiben wir in der Sprache (das muss in dieser Beweisrichtung für alle $i$ gelten, hier dürfen wir uns also kein $i$ aussuchen!).

Ist dagegen $y \neq a$, ist das Wort $$w=b^\star c^\star \in L_1$$ Egal, ob es dann überhaupt $b$'s gibt oder nicht, ob also $y=b$ oder $y=c$, die relative Anzahl an $b$'s und $c$'s ist im Fall, dass es keine $a$'s im Wort gibt nicht spezifiziert, also bleibt jedes beliebige $xy^iz$ in der Sprache.

Damit sind wir fertig: Für jedes Wort $w$ ab einer gewissen Größe gibt es eine Zerlegung mit (1), (2) und (3) erfüllt.

von Dozent (10.1m Punkte)  
Bearbeitet von
0 0
Ich glaube du hast dich vertippt. Du wolltest wahrscheinlich schreiben:
... Ist dagegen $y \neq a$, ist das Wort ....
0 0
Richtig, ich korrigere es. Danke.
...