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

1 Pluspunkt 1 Minuspunkt
125 Aufrufe

Hallo beisammen,

habe nicht direkt eine Frage zu der Aufgabe, sondern zum Pumping-Lemma:

1) Woher weiß ich n, die Anzahl der Zustände?
2) Wenn ich das Pumping-Lemma auf den Automaten L5 in AÜ-1-2 anwende, nehme ich bspw. als Wort 0000111. x auf die 0er, y auf die erste 1 und z auf die zwei restlichen 1er. Nun pumpe ich y. Dann bekomme ich mehr als 3 Einsen und der Widerspruch ist geführt. Was mache ich falsch? Denn es gibt ja in dieser Aufgabe einen EA, der L5 erkennt.


LG und danke im Voraus!

Andi

in AU-1-3 von uafjv uafjv Tutor(in) (168k Punkte)  

2 Antworten

1 Pluspunkt 0 Minuspunkte
Hallo,

1) die Anzahl der Zustände ist meist nicht bekannt. Man kann aber für jedes n ein längeres Wort kreieren, meistens indem einfach bestimmte Zeichen(folgen) n-mal wiederholt werden, z.B. 0^n.

2) Gültige Zerlegung: x = irgendeine Anzahl an Nullen; y = eine Null; z weitere Nullen und der Rest (bei deinem Beispiel 111). Dann kann y beliebig aufgepumpt werden. Generell besagt die Umkehrung des Pumpinglemmas (mit der wir den Widerspruch zeigen wollen), dass ein Wort nicht erkannt wird, wenn es überhaupt keine gültige Zerlegung mit den 3 Bedingungen gibt, dass also für jede Zerlegung das Aufpumpen verletzt ist. Irgendeine Zerlegung zu finden, die das Pumpinglemma verletzt, reicht also nicht aus.

MfG, Jakob
von uafjv uafjv Tutor(in) (168k Punkte)  
1 Pluspunkt 0 Minuspunkte

Hallo,

was hier sehr wichtig ist, und deshalb wiederhole ich es nochmal, obwohl es Jakob eigentlich schon gesagt hat, ist, dass man sich beim PPL nicht einfach Wörter konstanter Länge anschauen kann, denn diese kann man immer mit einem endlichen Automaten ohne Schleife erkennen. Habe ich ein Wort der Länge k, kann ich immer einen Automaten mit k+1 Zuständen bauen, der keine Schleife braucht und das Wort erkennt.

Anstelle einzelner Wörter betrachten wir beim PPL immer Wortklassen. Bspw. ist anbn nicht ein Wort, sondern abhängig von n eine beliebig große Menge von Wörtern. Jetzt können wir sagen, dass n von der Anzahl der Zustände des Automaten abhängt. Damit drehen wir den Spieß um, denn dann kann keiner sagen: Dann nehme ich halt einfach einen größeren Automaten. Wenn der Automat größer wird, wird eben auch das Wort länger. Die Grundidee des PPL ist dann, dass Wörter, die mindestens so lang sind wie die Anzahl der Zustände des Automaten, nur erkannt werden können, wenn der Automat eine Schleife hat. Und hat er eine Schleife, kann man diese beliebig oft durchlaufen, was einem "Pumpen" der Worts entspricht.

Viele Grüße

Lukas König

von uafjv uafjv Tutor(in) (168k Punkte)  
...