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

Beliebteste Tags

verständnis alternativlösung klausur kellerautomat endlicher-automat grammatik regulärer-ausdruck pumpinglemma turingmaschine tipp zahlendarstellung cmos klausurrelevant bonusklausur komplexität schaltwerk binary-decision-diagram deterministisch assembler schaltnetz sprachen minimierung nichtdeterministisch huffman fehler-in-aufgabe chomsky-normalform anwesenheitsübung rechtslinear heimübung flip-flop cocke-younger-kasami-algorithmus kontextsensitive-grammatik kontextfreie-grammatik huffman-kodierung hauptklausur fehlererkennbarkeit vorlesungsfolien kontextfreie-sprache polynomialzeitreduktion faq gleitkommazahl fehlerkorrigierbarkeit rechtslineare-grammatik dateiorganisation cache darstellung-klausur nachklausur xwizard adressierungsarten lambda mealy konjunktive-normalform pipelining zustände saalübung leeres-wort endliche-automaten ohne-lösungen betriebssystem speicherorganisation moore monotone-grammatik 2-komplement fehler reguläre-sprache hammingzahl monoton lösungsweg pumping-lemma-für-kontextfreie-sprachen kodierung berechenbarkeit klausureinsicht disjunktive-normalform pumping-lemma info-ii bussysteme rechnerarchitektur abzählbarkeit komplexitätsklassen ableitungsbaum vorlesungsaufzeichnung round-robin minimierung-endlicher-automaten chomsky-klassen binärzahl entscheidbar programmiersprachen entscheidbarkeit aufzählbarkeit stern-symbol automaten nukit-fragen bewertung zugriffsarten von-neumann-rechner umformung adressierung mengen binär-subtrahieren organsiation

Kategorien

1 Pluspunkt 0 Minuspunkte
105 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

 

in END-AZ von uqdrx uqdrx Eins-Komma-Null-Anwärter(in) (4.3k Punkte)  
0 0
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

1 Eine Antwort

1 Pluspunkt 0 Minuspunkte

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)

von uedqi uedqi Tutor(in) (109k Punkte)  
0 0
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
1 0
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)
...