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 0 Minuspunkte
281 Aufrufe

Hallo an Alle,


Ich frage mich, wieso bei den kontextfreien Sprachen immer gegeben sein soll, dass es zwei Pumpstellen bei hinreichend großen Wörtern gibt. Grundsätzlich habe ich das Konzept, dass bei längeren Wörtern als Anzahl an Zuständen vorhanden ist, es Schleifen in der Grammatik geben muss, verstanden. Nun wird aber (allen voran bei dem PPL der kontextfreien Sprachen) immer wieder erklärt, dass es (1) zwei Pumpstellen gibt, die (2) immer gleich groß sein sollen. Hier sind auch noch SC der Überlegung im Text und die dazugehörige Skizze, die das Ganze erläutert:



Nun verstehe ich nicht ganz, wieso es immer zwei Pumpstellen geben muss, bzw wieso die dann auch noch gleich groß sein sollen?
Im Kopf habe ich dabei immer eine kontextfreie Sprache, die ja auch in CNF dargestellt werden kann.
Nun habe ich mir eine Grammatik überlegt, die Wörter produziert, deren Länge die Anzahl der Zustände übertrifft:


Dabei habe ich in B eine Produktion von sich selbst, was mir die Schleifen eines PPL ermöglicht. Nun kann ich mein Wort ja wie unten beschrieben ableiten, ohne , dass neben dem grün markierten B links und rechts die gleiche Menge gepumpt wird. Da jede kontextfreie Sprache in CNF dargestellt werden kann, weiß ich also nicht, woher diese immer zwei gleich großen Pumpstellen genau herkommen sollen.

Ich würde mich sehr über jede Antwort freuen, 

Grüße!

in PUM-AA von uzmzu uzmzu Lernwillige(r) (260 Punkte)  

1 Eine Antwort

1 Pluspunkt 0 Minuspunkte
 
Beste Antwort

Hallo uzmzu,

mit dem PPL kannst du ja nur prüfen, ob eine Sprache nicht zu L1 (bzw. L3) gehört. 
Es kann natürlich sein, dass du nur eine Pumpstelle bei deiner Sprache hast, es ist ja nur Vorrausgesetzt, das bei z = uvwxy, |z| >= n und die Pumpstellen v,x mit |vx| >= 1 sein (und der dritten Bedingung). Also kann v oder x auch lamda sein.

Und natürlich können die Pumpstellen auch unterschiedlich oft gepumpt werdem. Aber man kann sie auch gleich oft pumpen und das gepumpte Wort muss immer noch in der Sprache sein. Also nur ein spezieller Fall. 

Dein Beispiel gehört zu L1, deshalb kann man mit dem PPL nicht zeigen, dass es nicht zur Sprache gehört

Es ist einfach nur das Vorgehen des PPL, dass es zwei Pumpstellen gibt, die gleich oft gepumpt werden. Deine angebrachten Punkte von dir sind für die Realisierung der individuellen Wörter des Sprache richtig.

Ich hoffe ich konnte dir weiterhelfen. Wenn es noch Unklarheiten gibt, schreibe einfach noch mal.

Viele Grüße

Anne (Tutor)

von uvlwv uvlwv Info-Genie (9.4k Punkte)  
ausgewählt von uzmzu uzmzu
...