6-END-AE: Bedeutung {0,1}*, leere Menge enthalten?

Question

Hallo,

bei Aufgabe 6-END-AE aus dem 1. Buch verstehe ich die Musterlösung nicht ganz. Der det. endliche Automat soll Wörter akzeptieren der Form 1u1 wobei u Element aus {0,1}*.

Ich dachte der Stern bedeutet an dieser Stelle die Menge aller Wörter bestehend aus beliebig vielen 0´en und 1´en, inklusive der leeren Menge.

Dann müsste das Wort "11" ja auch zu einem Endzustand führen und akzeptiert werden. In diesem Fall wäre u eben die leere Menge. Dies ist in der Musterlösung allerdings nicht der Fall.

Habe ich einen Denkfehler gemacht?

Answer 1

u kann leer sein, wie du richtig gesehen hast. Dies wird mit dem nichtdet. Automaten aber auch abgebildet. Bei dem Wort 11 kommt man mit der ersten 1 in den Zustand S1 und mit der zweiten 1 geht man in S2, den Endzustand über, also wird das Wort akzeptiert.