Reicht es bei dieser Aufgabe eigentlich aus, nur den Fall i = j zu betrachten? Wenn man für diesen Fall gezeigt hat das das Wort nicht regulär ist (ist das richtig ausgedrückt?), dann hat man diese Eigenschaft ja schon für die ganze Sprache ausgeschlossen.
Bei einem einzelnen Wort macht es keinen Sinn von regulär oder nicht regulär zu sprechen.
[Speziell: Wenn du ein Wort hast, dann kannst du für dieses stets einen Automaten konstruieren, der genau dieses Wort (und sonst nichts) akzeptiert - du speicherst die Präfixe des Wortes (was du bisher gelesen hast) in den Zuständen und die Kanten sind dann eben die einzelnen Buchstaben.]
Evtl. meinst du etwas anderes? Wendest du das Pumping Lemma an?
Cheers.
Ja, das pumping lemma wende ich an. Es ging mir hauptsächlich darum, das ich vermute, das es ausreicht für den Fall i = j das pumping lemma anzuwenden. Dan kann man den Beweis ähnlich wie im Skript führen. Jetzt besteht aber ja noch die Möglichkeit das i ungleich j aber j = k oder k = i ist. Und das man diese Fälle dann weglassen kann, darüber hätte ich Gerne gewissheit.
Soweit erstmal danke für deine Antwort.
Ja. Das uvw-Theorem sagt ja aus, dass für alle Wörter z mit |z|>n die drei Eigenschaften zutreffen. D.h. wenn du dir ein Wort suchst und das zum Widerspruch bringst, hast du gewonnen. Das Vorgehen ist analog zu dem in der Vorlesung.
wenn du die Menge L = {a^i b^j | i=j oder i != j} hast,
dann reicht es NICHT, für L2 = {a^i b^j | i=j} den Widerspruch per Pumpinglemma zu zeigen
und dann zu behaupten, L wäre nicht regulär
(eine reguläre Menge kann irreguläre Mengen als Teilmengen haben)
falls du sowas in der Richtung meinst,
aber was du genau meinst weiss mancher ja nicht
wenn du die Aufgabe nicht komplett beschreibst ;)
Hmm. Moment. Habe ich da was falsch verstanden?
Das Pumping-Lemma besagt doch: Wenn die Menge regulär ist, dann gibt es eine Zahl n, so dass jedes Wort z mit |z| >= n zerlegt werden kann und dann bestimmte Eigenschaften gelten. Ich kann also ein _belibiges_ Wort wählen. Also insbesondere auch (um bei deinem Beispiel zu bleiben) a^i b^i und es müssen dann die Eigenschaften gelten. Man kann doch nun zeigen, dass diese Eigenschaften nicht gelten und dann bedeutet das, dass diese Menge nicht regulär ist.
Ich bin mir zwar nicht sicher, aber dass eine reguläre Menge irreguläre Teilmengen haben kann ist mir neu. Anders herum ist es doch richtig, oder?
andersrum ist es auch richtig, ja,
in beide Richtungen ist die Teilmengen-Beziehung möglich,
Beispiel für die von mir betonte Richtung:
{a^i b^j} ist Teilmenge von L = {a^i b^j | i=j oder i != j} = (a* b*), welches ziemlich regulär ist
oder auch:
alle Wortmengen, auch die irregulären, sind Teilmenge von (a+b)*
(die Menge aller Wörter)
worauf ich etwas versteckt hinweisen wollte:
über das Pumpinglemma kann man vielleicht ein Wort finden,
das nicht mehr der Bedingung i=j genügt,
das aber trotzdem in der fraglichen Menge ist wenn es eine der ANDEREN Bedingungen erfüllt,
diese kann also nicht einfach vernachlässigen,
sondern man muss ein Wort finden das ALLE Bedingungen nicht erfüllt
Danke Slater, ich habe mir das nochmal überlegt und du scheinst recht zu haben.
Wir sollten übrigens zeigen das { a^i b^j a^k und i = j oder j = k oder k = i } nicht regulär ist.
Naja, klar. Ich kann mir nicht einfach ein n aussuchen und wenn |z|<n ist einfach sagen, dass die Menge nicht regulär ist.
Aber wenn man alles korrekt berücksichtigt, wird man schon den Widerspruch zeigen können. Da "deine" Menge allerdings regulär ist, wird man den natürlich nicht finden können.
In der konkreten Aufgabe hingegen kann man bei geschickter Wahl von i,j,k ein Wort aussuchen, für das i=j gilt und dann den Widerspruch machen.
Achja: Die Menge ist übrigens: [img]
http://mokrates.de/cgi-bin/texstring?L_%7B7.2(ii)%7D%20%3A%3D%20%5C%7Ba%5Eib%5Eja%5Ek%20%5Cmid%20i%2Cj%2Ck%20%5Cgeq%201%20%5Cwedge%20((i%3Dj)%20%5Cvee%20(j%3Dk)%20%5Cvee%20(k%3Di))%5C%7D[/img]
