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.)

Schöne Ferien!
 

 

allgemeine Fragen zum Pumping-Lemma

0 Punkte
83 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

Gefragt 22, Sep 2015 in AU-1-3 von uafjv uafjv Tutor(in) (167,990 Punkte)  

2 Antworten

+1 Punkt
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
Beantwortet 22, Sep 2015 von uafjv uafjv Tutor(in) (167,990 Punkte)  
+1 Punkt

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

Beantwortet 22, Sep 2015 von uafjv uafjv Tutor(in) (167,990 Punkte)  
...