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 0 Minuspunkte
213 Aufrufe
Guten Tag,

kann es sein, dass auf Folie 2-25 im zweiten Kapitel der Vorlesung ein Fehler in der Definition des Pumping-Lemmas vorliegt?

Bei Punkt (1) steht dort, dass Betrag(xy) kleiner gleich n ist. Müsste es aber nicht heißen, dass Betrag(xz) kleiner gleich n ist?

Falls es sich nicht um einen Fehler handelt, so würde ich mich über eine kurze Erklärung freuen, wieso dies so ist.

Viele Grüße
in Allgemeine Fragen von  

2 Antworten

1 Pluspunkt 0 Minuspunkte
 
Beste Antwort
Hello,

es ist kein Fehler. Um y zu bekommen, das sich beliebig pumpen lässt, reicht es aus nur bis die ersten n Zeichen von w zu betrachten. Schauen Sie bitte auch die Folie 26 an.

Pradyumn Shukla
von Pradyumn Shukla Dozent (10.0m Punkte)  
ausgewählt von
0 0
Danke für die schnelle Antwort! Ich verstehe allerdings auch mit Folie 26 nicht ganz, wieso dort k kleiner gleich n sein muss. Dass dann Betrag(xy) kleiner gleich n ist, macht Sinn, aber wieso ist k kleiner gleich n?
Mich verwirrt z.B., dass dann dieser Automat ja nicht dem Lemma entsprechen würde:
- Automat mit drei Zuständen
- solange ich a eingebe, bleibe ich in s0
- wenn ich b eingebe, springe ich in s1 und bleibe dort, solange b eingegeben wird
- wenn ich c eingebe, springe ich in s2 und bleibe dort, solange c eingegeben wird
- c ist Endzustand
Wenn ich jetzt z.B. das Wort w = abbbbbbc (Betrag von w = 8) eingebe, dann wird dieses ja eigentlich vom Automaten akzeptiert und ich brauche nur die drei Zustände (n = 3) des endlichen Automaten. Aber Betrag von (xy) wäre in diesem Fall = 7 und damit größer als n, oder nicht?
Ich hoffe, dieses Beispiel ist nachvollziehbar. Was ist an diesem Beispiel falsch?
Viele Grüße
0 0
Die Schleife kann aber schon nach drei Schritten auftreten. Genauer: Muss (laut PPL) auftreten können. Lesen Sie sich das Kapitel im Lehrbuch durch!
0 Pluspunkte 0 Minuspunkte
Haben Sie sich dieses Kapitel mal im Lehrbuch durchgelesen? Beim Pumping-Lemma, das vielen Studierenden anfangs Probleme bereitet, haben wir besonders darauf geachtet, eine schlüssige und einfache Beschreibung zu formulieren. Ich bin mir sicher, dass Sie es nach der Lektüre verstehen werden.
von Dozent (10.1m Punkte)  
0 0
Danke erneut für diese super-schnelle Antwort. Ich glaube, ich habe meinen Verständnisfehler gefunden. Bei y handelt es sich nur um den ersten Durchlauf der Schleife, jeder weitere Durchlauf zählt nicht zu y, sondern es ergibt sich yy, yyy, yyyy usw.
Ist das korrekt?
Tatsächlich ist das im Lehrbuch klarer formuliert, danke für den Hinweis. Leider haben wir Studenten nicht die Zeit, jedes Thema auch im Lehrbuch durchzuarbeiten, da wir dafür einfach zu viele Fächer gleichzeitig belegen müssen. An dieser Stelle war es aber auf jeden Fall hilfreich :D
Viele Grüße und schönen Abend :)
0 0
Ja, genau, mindestens der erste. Es können auch mehrere sein, denn ein EA mit vielen Zuständen kann trotzdem sehr schnell eine Schleife produzieren - muss er aber nicht. Spätestens nach $n$ Übergängen kommt aber auf jeden Fall eine.
...