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

0 Pluspunkte 0 Minuspunkte
317 Aufrufe
Wozu steht leere menge stern im regulären Ausdruck?

Wie kann man aus solchen komplexen detEAs den regularen Ausdruck finden. Wie geht man also Schritt für Schritt vor?
in Band I, Kapitel 2 von  
0 0
Können Sie die Frage bitte in die korrekte Kategorie verschieben? Die Kategorie sollte immer die ID der Aufgabe sein, also in diesem Fall wahrscheinlich END-AA oder so ähnlich.

1 Eine Antwort

0 Pluspunkte 0 Minuspunkte

Die Stern steht für die Iteration der leeren menge, also das leere Wort. In unserem Beispiel funktioniert das folgendermaßen:

In der ersten Klammer (000*+∅*) steht 000* für mindestens 2 Nullen, es können danach aber  beliebig viele geschrieben werden..  + (oder)  ∅* für nichts (leeres Wort).   

Für die letzte Klammer gilt das gleiche. Entweder 1 oder 10 oder das leere Wort (∅*). Über ∅* haben wir quasi die Möglichkeit die Klammer zu "löschen bzw. auszulassen"

(Beachten sollte man auch, dass das leere Wort hier nur als Term über ein Produkt mit dem Rest des regulären Ausdrucks verbunden ist. Deswegen ist das leere Wort selbst nicht Teil der Sprache)

 

Leider gibt es keine Schritt für Schritt Anleitung um von einem endlichen Automaten auf einen regulären Ausdruck zu kommen. In der Regel hilft es sich den nichtdeterministischen Automaten anzuschauen und sich zu überlegen über welche Pfade Wörter akzeptiert werden können. 

 

Viele Grüße

Niklas (Tutor)

von Niklas Hasebrook Tutor(in) (101k Punkte)  
...