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.)

Schöne Ferien!
 

 

Verständnisproblem: Reguläre Ausdrücke

+1 Punkt
78 Aufrufe
Hallo zusammen,
 
 
leider verstehe ich beim regulären Ausdruck nicht den fett markierten Teil mit den 3 Oern:
 
alpha=(000* +leere Menge*)1(0+1)*0
 
 
 
Mit der ersten 0 gehe ich doch in s1 und mit der zweiten gehe ich entweder aus s1 oder bleibe in Endzustand s1.
 
 
 
Wenn ich aber wieder aus s1 rausgehe, macht die 3 0, die beliebig oft vorkommen kann, leider gar keinen Sinn für mich....
 
 
 
Mfg

 

Gefragt 5, Feb 2016 in END-AZ von uqdrx uqdrx Eins-Komma-Null-Anwärter(in) (4,290 Punkte)  
Hallo zusammen,


leider verstehe ich beim regulären Ausdruck nicht den fett markierten Teil mit den 3 Oern:

alpha=(000* +leere Menge*)1(0+1)*0



Mit der ersten 0 gehe ich doch in s1 und mit der zweiten gehe ich entweder aus s1 oder bleibe in Endzustand s1.



Wenn ich aber wieder aus s1 rausgehe, macht die 3 0, die beliebig oft vorkommen kann, leider gar keinen Sinn für mich....



Mfg

Eine Antwort

+1 Punkt

Hallo uqdrx!

Du musst den Regulären Audruck hier ein bischen "anders lesen".

Der komplette Ausdruck lautet ja:

alpha = (000* +leere Menge*)1(0+1)*0  +   00*(1+10+leere Menge*)

Wie du anhand der farbigen Markierung siehst, zerfällt alpha in 2 verschiedene Möglichkeiten in einen Endzustand zu gelangen:

1. Möglichkeit: Du kannst direkt mit einer 1, dann einer 0 oder einer 1, und am Ende mit einer 0 von s0 aus in den Endzustand s4 übergehen, wobei du ganz am Anfang beliebig oft die Schleife s0 - s1 durchlaufen kannst (das ist der Teil  000*, der dich so verwirrt hat).

2. Möglichkeit: Du gehst mit einer 0 von s0 in s1, bleibst da beliebig lange mit der Eingabe weiterer Nullen (0*) oder gehst anschließend in den Zusand s4 weiter (das ist die Klammer (1+10+leere Menge*)).

Dein eigentlicher Verständnisfehler liegt also darin, dass der gelbmarkierte Teil nicht den Weg beschreibt, um in den Endzustand s1 zu kommen, sondern wie man in den Endzustand s4 gelangt.

Ich hoffe, das hilft dir weiter!

Viele Grüße,

Janine (Tutorin)

Beantwortet 5, Feb 2016 von uedqi uedqi Tutor(in) (108,510 Punkte)  
Hey Janine,

zunächst Mal vielen Dank für deine Erklärung.

Bei den 3 Oern verstehe ich aber die ANordnung nicht...

Meiner Ansicht nach müssten diese wie folgt angeordnet sein 0 0* 0.

Mit der 0* kann ich im Endzustand s1 belieblig oft bleiben bis ich wieder rausgehe.

Die Anordnung der Musterlösung ist jedoch

0 0 0*

D.h. ja ich gehe von s0 --> s1 gehe dann wieder von s1--> s-->0 und dann wenn ich meine 0 nur einmal wiederhole bin ich ja wieder in s1, aber ich möchte ja zu s4...

Mfg
Hallo uqdrx!

Es ist egal, ob du 000* oder 00*0 schreibst!

Beide Varianten besagen, dass du mindestens 2 Nullen hast (einmal von s0 nach s1 und dann von s1 nach s0), aber es können eben auch mehr Nullen eingegeben werden (dh. Schleife bei s1).

Deine Variante 00*0 ist sozusagen die direkt aus dem Automaten abgelesene Version, 000* ist die vereinfachte Version (in dem Sinne, dass 0*, was ja die optionalen Zusatznullen beschreibt, ans Ende geschrieben wurde).

Ich hoffe, das hilft dir weiter!

Viele Grüße,
Janine (Tutorin)
...