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

Was passiert bei $m=0$?

+1 Punkt
28 Aufrufe

Hallo,

was würde denn passieren, wenn ich für $m=0$ wähle? Nach Definition ist das ja zulässig. In diesem Fall würde ich  ein Wort haben, welches nur aus $a^n$ besteht, und ich könnte beliebig pumpen. Damit hab ich aber meinen Beweis ja entkräftet, weil ich ein Gegenbsp gefunden habe.

 

Gefragt 29, Sep 2015 in 2008-N-02 von uafjv uafjv Tutor(in) (167,990 Punkte)  
Bearbeitet 10, Okt 2015 von Lukas König

Eine Antwort

0 Punkte

Solch ein Bespiel wie das von dir angeführte $w=a^n$ entkräftet deinen Beweis nicht. Das Pumpinglemma sagt aus, dass man ALLE Wörter w einer regulären Sprache mit $|w| \geq n$ gemäß der Angaben im Lemma so zerlegbar sind, dass man entsprechend pumpen kann.

Das Pumpinglemma schließt nicht aus, dass nicht-reguläre Sprachen oder eine Teilmenge einer nicht-regulären Sprache trotzdem das Pumpinglemma für reguläre Sprachen erfüllen können (siehe dazu auch Heimübung 3, Aufgabe 4).

Der Beweis, dass eine Sprache nicht regulär ist, ist ein Widerspruchsbeweis. Bei einem Widerspruchsbeweis reicht ein einziges Beispiel, das zu einem Widerspruch zur Annahme führt, aus, um die Annahme zu widerlegen.

Tobias (Tutor)

 

Beantwortet 29, Sep 2015 von uafjv uafjv Tutor(in) (167,990 Punkte)  
Bearbeitet 10, Okt 2015 von Lukas König
...