Beweisidee: Wenn L* regulär ist, dann muss L nicht notwendigerweise regulär sein |
| 04.04.2009, 17:24 | Auf diesen Beitrag antworten » |
| Gast | 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 |
|
|
|
| 06.04.2009, 19:56 | Auf diesen Beitrag antworten » |
| Ich | 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). |
|
|
