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

a): Widerspruchsbeweis möglich?

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

 

Gefragt 17, Sep 2015 in HU-1-4 von uafjv uafjv Tutor(in) (167,990 Punkte)  

2 Antworten

0 Punkte

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)

 

Beantwortet 17, Sep 2015 von uafjv uafjv Tutor(in) (167,990 Punkte)  
0 Punkte

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)

 

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