Aufgabe 20

Question

Wozu steht leere menge stern im regulären Ausdruck?

Wie kann man aus solchen komplexen detEAs den regularen Ausdruck finden. Wie geht man also Schritt für Schritt vor?

Comments

Können Sie die Frage bitte in die korrekte Kategorie verschieben? Die Kategorie sollte immer die ID der Aufgabe sein, also in diesem Fall wahrscheinlich END-AA oder so ähnlich.

Answer 1

Die Stern steht für die Iteration der leeren menge, also das leere Wort. In unserem Beispiel funktioniert das folgendermaßen:

In der ersten Klammer (000*+∅*) steht 000* für mindestens 2 Nullen, es können danach aber  beliebig viele geschrieben werden..  + (oder)  ∅* für nichts (leeres Wort).   

Für die letzte Klammer gilt das gleiche. Entweder 1 oder 10 oder das leere Wort (∅*). Über ∅* haben wir quasi die Möglichkeit die Klammer zu "löschen bzw. auszulassen"

(Beachten sollte man auch, dass das leere Wort hier nur als Term über ein Produkt mit dem Rest des regulären Ausdrucks verbunden ist. Deswegen ist das leere Wort selbst nicht Teil der Sprache)

 

Leider gibt es keine Schritt für Schritt Anleitung um von einem endlichen Automaten auf einen regulären Ausdruck zu kommen. In der Regel hilft es sich den nichtdeterministischen Automaten anzuschauen und sich zu überlegen über welche Pfade Wörter akzeptiert werden können. 

 

Viele Grüße

Niklas (Tutor)