regulären Ausdruck nachweisen - Seite 2 |
| 22.11.2007, 00:13 | Auf diesen Beitrag antworten » |
| Tobias | Ganz genau. 
Myhill Nerode verallgemeinert und formalisiert deine informelle Begründung übrigens, indem er Wörter in Äquivalenzklassen bezüglich der Nerode-Relation aufteilt. Gibt es unendlich viele Äquivlaenzklassen so ist die Sprache nicht regulär, weil sie nicht durch einen endlichen Automaten darstellbar ist. Das Pumping-Lemma ist eine ähnliche Argumentation: Durchläuft ein Automat mit m Zuständen das Eingabewort mit Länge n > m, muss er nach max. m+1 Zeichen in einem schon besuchten Zustand landen. Das impliziert, dass er eine Schleife gelaufen ist. Die Schleife kann man nun immer wieder in der gleichen Weise durchlaufen, was genau dem "Aufpumpen" des Teilwortes entspricht. |
|
|
|
|
|
