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