---

Geschrieben von Klinger am 26.11.2017 um 11:29:

  Reguläre Sprache prüfen

Hallo Liebe Freunde,
ich habe zwei Fragen zu regulären und kontextfreien Sprachen, die ich gerne beantwortet haben möchte.

Gezeigt und allseits bekannt ist, dass a^n b^n keine reguläre Sprache ist.
Nun möchte ich gerne wissen, ob die folgenden zwei Sprachen reguläre Sprachen sind:
1) a^m b^n mit m!=n. Hier bin ich mir unsicher, zwar ist die Bedingung mit m=n wie im obigen Beispiel nicht mehr gegeben, aber trotzdem würde ja ein Speicher erforderlich sein, der mitzählt, wie viele m es gab und dass n nicht das gleiche ist. Das wäre ja dann doch das gleiche Problem wie oben, was das ganze zu einer nichtregulären Sprache macht.

2) Wenn ich {a^n b^n} und {e} (Epsilon} miteinander vereinige, ist das ganze dann regulär? Ich wüsste nicht, was das ganze auf einmal regulär machen sollte, aber ich bin mir da nicht sicher.

Hat da jemand Ideen?
Grüße

---

Geschrieben von Karlito am 27.11.2017 um 09:08:

 

Hallo Klinger,

zu 2) Ich denke hier kann man das Pumping-Lemma weiterhin verwenden. Im Prinzip ändert sich ja nichts. Du nimmst Worte mit einer Mindestlänge her und weist nach, dass es dafür dann keine Zerlegung uvw gibt. Es kommt ja nur ein Wort der Länge 0 hinzu, das sollte den Rest nicht ändern.

zu 1) Angenommen a^nb^m mit n!=m wäre regulär, dann wäre das Komplement auch regulär (Abschlusseingenschaften von regulären Sprachen). Das Komplement ist die Sprache aus 2). Wenn 2) also nicht regulär ist, und 1) das Komplement von 2), dann kann 1) nicht regulär sein.

Das sind zumindest Ansätze.

Besten Gruß,

Karlito