Sicher, das dies den Automaten darstellen soll ?
Dann stimmt aber etwas mit der Defintion der Sprache nicht.
Also ich hätten den Automaten ja so beschrieben
A := (Z, S, s0, d, F)
Z := {0, 1}
S := {A, B, C, D, E, F, G}
s0 := A
F := {F}
d ergibt sich aus der graphischen Darstellung:
Code:
1
--------->
0 1 0 0 _ 1
A ---> B ---> C ---> D E ---> |F| ---> G
¯
<--- <---
1 0
oder (verkürzt) so:
A := (Z, S, s0, d, F)
Z := {0, 1}
S := {A, B, C, D, E}
s0 := A
F := {E}
d ergibt sich aus der graphischen Darstellung:
Code:
0 1 1 0 _
A ---> B ---> C ---> D ---> |E|
¯
<--- <---
0 1
Sei L := { 01 (01)^m 10 (10)^n | n,m => 0 }
Angenommen du wählst n =5, dann hast du wegen x Element von L und |x| >= 5 als mögliche Werte
01 10 10 (10)^n , n => 0
01 01 10 (10)^n , n => 0
Wegen |uv| <= n, also |uv| <=5 und |v| => 1 bleiben für uv nur folgende Werte übrig:
0
01
011
010
0110
0101
01101
01011
Und wie man sieht kann man eine Folge bestimmen für die es gilt.
Zum Beispiel:
0110 mit v = 10
0101 mit v = 01
Damit es nicht gilt dürfte es aber gar keine Folge geben für dies es funktioniert, da dieses Lemma nur verlangt, dass es überhaupt eine Folge gibt für die es funktioniert. Wenn man es mit Quantoren schreibt sieht man es deutlicher:
Sei L keine nicht reguläre Sprache und Z* ihre Zeichenmengen ohne das leere Wort, dann gilt die folgende Aussage.
Es existiert ein n > 0 für alle x Element von L so das gilt: |x| >= n. Daraus folgt, dass u,v,w Elemente von Z* mit folgenden Eigenschaften existieren: x = uvw und |v| > 0 und |uv| <= n. Des weiteren gilt für alle i >= 0, dass u v^i w ein Element von L ist.
Das Pumping Lemma gilt i.d.R immer dann nicht, wenn sich die Sprache etwas "merken" müsste, da dies reguläre Sprachen nicht können.
Wäre also n = m gesetzt, dann würde es nicht funktionieren.
Es läuft hier also nur auf
L' := { (01)^m (10)^n | n,m > 0 }
zurück und nicht auf
L' := { (01)^n (10)^n | n > 0 }
weshalb das Pumping Lemma hier funktioniert.
Ferner kann man sogar sagen, dass es eine reguläre Sprache ist.
Dies ist aber sogar offensichtlich, da du einen endlichen Automaten konstruieren kannst, denn:
Eine Sprache L heißt regulär, wenn sie eine der folgenden äquivalenten Bedingungen erfüllt:
- L wird von einer regulären Grammatik erzeugt.
- L wird von einem endlichen Automaten akzeptiert.
- L kann durch einen regulären Ausdruck dargestellt werden.
Deshalb is das so umständlich mitm Sternchen[/Klugscheißmodus]
