Erklärung des regulären Ausrucks?

Question

Ich verstehe die regulären Audrücke einfach nicht. Ich habe jetzt schon einige Aufgaben dazu gemacht, auch welche aus dem Übungsbuch aber ich komme in den seltesten Fällen auf das richtige Ergebnis. Gibt es eine Art grundsätzliche Vorgehen?

Warum heißt es beispielsweise bei der b) 111*0 und nicht 11*10? Es reicht doch wenn ich vom Endzustand (in dem ich nach 1*0 bin) eine 1 in s2 gehe, dann beliebig viele 1er in s2, dann die 1 um in s0 zu kommen und wiederum die 0 um zurück im Endzustand zu sein.

Würde mich freuen, wenn jmd. vielleicht ein bisschen Licht ins Dunkle bringen könnte.

 

Answer 1

Hallo,

erst mal zur grundlegenden Vorgehensweise. Am schlausten ist es, sich für die regulären Ausdrücke den nichtdeterministischen Automaten anzugucken, da man hier am leichtesten einen regulären Ausdruck ableiten kann. Am Anfang guckst du immer nach Wegen, mit denen du vom Startzustand den Endzustand erreichst (hier 1*0). Anschließend betrachtest du Zyklen, mit denen du aus dem Endzustand herauskommst und anschließend wieder herein. In diesem Beispiel gibt es drei Stück.

- 0* (mit dieser Eingabe bleibe ich im Endzustand)

- (0+1)1*0  (mit dieser Eingabe gelange ich in S1, schreibe beliebig viele 1en und mit der 0 wieder in den Endzustand)

- 111*0 (mit der ersten 1 gelange ich in s2, dort beliebig viele 1en nacheinander, mit der letzten 1 zurück nach s0 und mit der 0 wieder in den Endzustand)

Diese Zyklen können alle beliebig oft und in beliebiger Reihenfolge wiederholt werden. Deshalb des * am Ende der großen Klammer.

Prinzipiell hast du mit deiner Aussage natürlich Recht: 11*10 ist der Ausdruck der sich intuitiv ergibt. Wenn du allerdings mal genauer hinschaust, kann man mit 11*10 und 111*0 genau die gleichen Wörter erzeugen. Es macht also keinen Unterschied, ob das Sternchen zur 1. 2. oder 3. 1 gehört. Von daher wäre deine Lösung sicherlich auch richtig.

Max (Tutor)