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 1 Minuspunkt
76 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.

 

in 2013-H-01 von uafjv uafjv Tutor(in) (168k Punkte)  

1 Eine Antwort

0 Pluspunkte 0 Minuspunkte

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)

 

von uafjv uafjv Tutor(in) (168k Punkte)  
beide Variante zusammen
...