Theoretische und technische Informatik - ganz praktisch
Herzlich willkommen auf der Question/Answer-Plattform zu Grundlagen der Informatik II. Wir wünschen Ihnen viel Spaß beim Lernen und Diskutieren!
Loggen Sie sich mit Ihrem KIT-Account (u...) ein, um loszulegen!
Beachten Sie auch diese Informationen zum Schnelleinstieg.
(Nicht-KIT-Studierende beachten bitte diese Informationen.)

Erklärung des regulären Ausrucks?

–1 Punkt
63 Aufrufe

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.

 

Gefragt 25, Sep 2015 in 2013-H-01 von uafjv uafjv Tutor(in) (167,990 Punkte)  

Eine Antwort

0 Punkte

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)

 

Beantwortet 25, Sep 2015 von uafjv uafjv Tutor(in) (167,990 Punkte)  
beide Variante zusammen
...