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 minimierung sprachen nichtdeterministisch huffman chomsky-normalform fehler-in-aufgabe anwesenheitsübung rechtslinear heimübung flip-flop cocke-younger-kasami-algorithmus kontextsensitive-grammatik kontextfreie-grammatik fehlererkennbarkeit huffman-kodierung hauptklausur vorlesungsfolien kontextfreie-sprache polynomialzeitreduktion faq gleitkommazahl fehlerkorrigierbarkeit rechtslineare-grammatik dateiorganisation cache darstellung-klausur nachklausur xwizard adressierungsarten lambda mealy endliche-automaten konjunktive-normalform pipelining zustände saalübung leeres-wort 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 pumping-lemma klausureinsicht disjunktive-normalform info-ii bussysteme rechnerarchitektur abzählbarkeit komplexitätsklassen ableitungsbaum vorlesungsaufzeichnung round-robin entscheidbarkeit minimierung-endlicher-automaten chomsky-klassen von-neumann-rechner binärzahl entscheidbar programmiersprachen aufzählbarkeit stern-symbol automaten schaltnetze-und-schaltwerke nukit-fragen bewertung zugriffsarten umformung adressierung mengen binär-subtrahieren

Kategorien

0 Pluspunkte 1 Minuspunkt
87 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
...