a): Widerspruchsbeweis möglich?

Question

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

 

Answer 1

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)

 

Answer 2

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)