---

Geschrieben von Gast am 04.04.2009 um 17:24:

  Beweisidee: Wenn L* regulär ist, dann muss L nicht notwendigerweise regulär sein

Hallo,

ich muss beweisen: Wenn L* regulär ist, dann muss L nicht notwendigerweise regulär sein.

Wenn ich via Kontraposition herangehe, brauche ich eine Sprache die nicht regulär ist, aber deren Kleene Star regulär ist.

Ich habe mir bis jetzt erfolglos den Kopf zerbrochen auf der Suche nach einer solchen Sprache. Hat jemand eine Idee?

Danke euch im Voraus

---

Geschrieben von Ich am 06.04.2009 um 19:56:

  RE: Beweisidee: Wenn L* regulär ist, dann muss L nicht notwendigerweise regulär sein

Wenn ich mich recht erinnere, ist die Menge aller Wörter, die nur aus dem Zeichen "x" bestehen, aber genau so viele "x" enthalten, dass deren Anzahl gleich der Fakultät einer natürlichen Zahl ist (also L={x^(n) : n=m!, m element IN), nicht regulär, da "gezählt werden muss".

Jedoch ist die Sprache L* durchaus regulär, da sie alle Wörter enthält, die nur aus dem Zeichen "x" bestehen, aber beliebig lang sind (da 1!=1, kann man sich alle beliebigen Längen zusammenbauen).