Hi,

in der aufgabe 7.2 war mit hilfe des pumping lemmas zu zeigen, dass die menge L7.2(ii) := {a^ib^ja^k | i, j, k ≥ 1 und (i = j)oder(j = k)oder(k = i)} nicht regulär ist.
in der musterlösung wurde gezeigt, dass dies für n>1 keine zerlegung gibt, die den kriterien des uvw-theorems entsprechen. soweit ist mir das auch klar, aber müsste nicht auch n=1 gezeigt werden, dass es keine zerlegung gibt? es muss doch für alle n element N gezeigt werden, dass eine solche zerlegung nicht gibt. man kann n=1 nicht weglassen….oder doch?

hab noch eine ergänzung zu meiner frage:
könnte man den beweis auch folgendermaßen führen:
die menge ist: L7.2(ii) := {a^ib^ja^k | i, j, k ≥ 1 und (i = j)oder(j = k)oder(k = i)}
n ist das n aus dem pumping lemma und ich wähle das wort a^n b^n a^m, wobei m= n+n ist. dieses wort muss in der menge sein, weil i=j.
die zerlegung uv kann nur aus a's bestehen, da uv kleiner oder gleich n sein muss. v muss min. ein a sein, da v ungleich 0. wenn man nun "hochpump" ist sofort i ungleich j. da j=n und k=n+n, gilt weiter j ungleich m. es ist möglich, dass bei einem bestimmten v^i i=k gilt. dies kann aber nur bei einem bestimmten i gelten, da m ja fest ist.
also kann die 3. bedingung des pumping lemmas nicht erfüllt werden und die menge ist somit nicht regulär.
dieser beweis unterscheidet sich etwas von dem in der musterlösung, aber er gilt für alle n element N.
ist dieser beweis auch ok oder geht das so nicht?

meinst du n = Zahl aus dem Pumping-Lemma?
für n=1 wäre dann ja der Startzustand auch Endzustand -> lambda e L -> kann nicht diese Sprache sein, fertig
(oder kein Endzustand, Sprache leer, auch nicht diese Sprache)

also eher ein trivialer Beweis, den man in der Musterlösung weglassen kann,
(in der Klausur besser nicht ;) )

dein Beweis ist wohl ok,
einfacher und genauer (ohne diese umständliche Beschreibung) wärs vielleicht schöner:

uvw = a^n b^n a^2n

durch pumpen
ist uw (ohne v) = a^n-x b^n a^2n mit x > 0, also i!=j, j!=k, k!=i
und zwar für alle Zerlegungen und beliebiges n > 0

wenn ich das Pumpinglemma richtig erinnere,
mit v weglassen hast du also weniger das Problem "es ist möglich, dass bei einem bestimmten v^i i=k gilt"

——-

zu "es ist möglich, dass bei einem bestimmten v^i i=k gilt":
man sollte eine Variable nicht für 2 verschiedene Dinge verwenden..

jo, danke. so ohne v (also v^i wobei i=0) gefällt mir der beweis wesentlich besser.