@alle -> -ist der Anfang korrekt, verständlich + sinnvoll
- die Formattierung ist ja auch nicht festgelegt, wie
glaubt ihr seht es am besten aus
-> bitte um Kommentare <-
Ich kommentiere den Text mal direkt:
Eine Menge M ist nicht regulär, wenn sie sich nicht durch einen endlichen Automaten (FA) darstellen lässt. Ein endlicher Automat A hat nur eine endliche Menge von Zuständen Z.
Das ist zwar richtig, aber hinterher wird ein buchstabierender
oder deterministischer Automat verwendet (weil nur dort mit jeder
Kante genau ein Symbol gelesen wird). Also sollte erwähnt werden,
dass angenommen wird, es gäbe einen buchstabierenden NFA oder
einen DFA für die Sprache.
Mit Hilfe des Beispiels der Sprache DUP, die nicht regulär ist, können wir zeigen das eine Beschreibung mit Hilfe eines FA nicht möglich ist.
DUP:={a^n b^n| n ist Element der natürlichen Zahlen N}
Wenn wir jetzt ein festes k (k ist Element der natürlichen Zahlen N) für die Zahl der Zustände auswählen,
Ich glaube, mit der Formulierung versteht man nicht, was eigentlich
das Argument ist (d.h. ich würde es nicht verstehen, wenn ich nicht
wüsste, was du sagen willst [img]
http://www.fb18.de/gfx/23.gif[/img]). Besser wäre vielleicht:
Angenommen, es gäbe einen {DFA, buchstabierenden NFA}. Dann sei
k die Anzahl seiner Zustände.
dann muss es solche i < k geben für die gilt a^i b^i führt zu einem Zustand innerhalb des Automaten mit der Anzahl der Zustände k.
Was willst du damit sagen? Wird die Aussage später benutzt?
…doch damit ist nicht mehr klar wieviele Zustände besucht wurden!
Auch hier ist evtl. unklar, was gemeint ist. Alternativ:
nach Lesen von [img]
http://mokrates.de/cgi-bin/texstring?a%5E%7Bk%2B1%7D[/img] wird ein bestimmter Zustand
zum zweiten Mal durchlaufen, also wird auf weitere
Symbole reagiert, als wäre bisher ein Wort der Form
[img]
http://mokrates.de/cgi-bin/texstring?a%5E%5Cell[/img] mit [img]
http://mokrates.de/cgi-bin/texstring?%5Cell%5Cle%20k[/img] gelesen worden, d.h. nach Lesen von [img]
http://mokrates.de/cgi-bin/texstring?b%5E%5Cell[/img]
wird akzeptiert, also wird [img]
http://mokrates.de/cgi-bin/texstring?a%5E%7Bk%2B1%7Db%5E%5Cell[/img] akzeptiert.
Der Automat mit k Zuständen kann also überlistet werden.
Beispiel: k = 4 i = 6 j = 2 Es wird also der gleiche (End-)zustand erreicht wie mit i=j=2!
Das muss nicht so sein! Nach dem Lesen des 6-ten a muss der Automat
nicht unbedingt in den Zustand, der beim Lesen von aa erreicht ist.
Das Schubfachprinzip sagt nicht, dass der Automat wieder von vorne
anfängt, sondern nur, dass er in irgendeinen Zustand kommt, in dem
er schon war.
Und schließlich sollte vielleicht kurz darauf hingewiesen werden,
dass das kein Beispiel zur Anwendung des Lemmas ist, sondern
dass die Idee des Lemmas benutzt wurden, um Nichtregularität
nachzuweisen.
