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

1 Pluspunkt 1 Minuspunkt
24 Aufrufe

Hallo,

habe eine allgemeinere Frage zum Punmping Lemma. Da das doch ein Widerspruchsbeweis ist, müsste es doch eigentlich auch klappen, dass man nur ein Gegenbeispiel anführt.

Also am Beispiel von Aufgabe a):

1. Annahme: Es existiere eine EA mit n Zuständen, der L3 akzeptiert.

Das Wort w = aaaa ist Element von L3 (i=2).

2. Aufteilung von w. w=xyz mit
x = Lamda (leeres Wort)
y = a
z = aaa

3. Dann müsste \( xy^{2}z \) auch Element von L3 sein, aber
\( xy^{2}z = aaaaa \), also nicht Element von L3, da sich kein i finden lässt, dass dieses Wort erzeugt.

-> Widerspruch, L3 ist nicht regulär.

Geht das?

Grüße, Julian

 

in HU-1-4 von uafjv uafjv Tutor(in) (168k Punkte)  

2 Antworten

0 Pluspunkte 0 Minuspunkte

Hallo Julian,

ganz so einfach geht das leider nicht. In deinem Fall hast du gezeigt, dass das ganze für i=2 nicht gilt, also für einen Spezialfall. Du müsstest das theoretisch für alle n aus den natürlichen Zahlen machen, um das ganze komplett zu beweisen. 

Es muss beim Pumping-Lemma also immer gezeigt werden, dass es für ein variables n gilt.

Ich hoffe, ich konnte dir helfen.

Max (Tutor)

 

von uafjv uafjv Tutor(in) (168k Punkte)  
0 Pluspunkte 0 Minuspunkte

Nein, das geht aus 2 Gründen nicht:

1. Für dein Wort ("aaaa") gilt die Bedingung \( |w| \leq n \) nur für \( n \leq 4 \). Wie bereits oben vom den Übungsleitern und mir erklärt, kann das n/die Anzahl Zustände des EA aber beliebig groß sein und darf im Beweis nicht auf einen festen Wert gesetzt werden.

2. Das Pumpinglemma sagt nur aus, dass (mindestens) eine Aufteilung xyz existiert, bei der man das y pumpen kann. Das heißt nicht, dass man bei jeder Aufteilung das y pumpen kann und das entstandene Wort noch in der Sprache ist. Du musst also für den Widerspruch zeigen, dass keine solche Aufteilung existiert. Eine einzelne Aufteilung heraus zu greifen, reicht nicht aus, da es eine  andere Aufteilung geben kann, mit der das Pumpinglemma erfüllt ist.

Grüße,

Tobias (Tutor)

 

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