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 turingmaschine pumpinglemma tipp zahlendarstellung cmos bonusklausur klausurrelevant 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 huffman-kodierung cocke-younger-kasami-algorithmus kontextsensitive-grammatik kontextfreie-grammatik fehlererkennbarkeit hauptklausur vorlesungsfolien polynomialzeitreduktion kontextfreie-sprache faq gleitkommazahl fehlerkorrigierbarkeit rechtslineare-grammatik dateiorganisation cache darstellung-klausur nachklausur xwizard adressierungsarten mealy lambda endliche-automaten konjunktive-normalform pipelining zustände saalübung leeres-wort moore ohne-lösungen betriebssystem speicherorganisation monotone-grammatik 2-komplement hammingzahl lösungsweg fehler pumping-lemma-für-kontextfreie-sprachen pumping-lemma reguläre-sprache monoton kodierung berechenbarkeit klausureinsicht disjunktive-normalform abzählbarkeit info-ii bussysteme rechnerarchitektur entscheidbarkeit komplexitätsklassen chomsky-klassen ableitungsbaum vorlesungsaufzeichnung round-robin aufzählbarkeit minimierung-endlicher-automaten von-neumann-rechner binärzahl entscheidbar programmiersprachen stern-symbol automaten schaltnetze-und-schaltwerke nukit-fragen bewertung zugriffsarten umformung adressierung mengen binär-subtrahieren

Kategorien

0 Pluspunkte 0 Minuspunkte
26 Aufrufe
Wie lese ich ein?

Können Sie Schritt für Schritt erklaren?

                                 Danke
in 2016-B-02 von uqyxt uqyxt Lernwillige(r) (640 Punkte)  

1 Eine Antwort

0 Pluspunkte 0 Minuspunkte
Hallo uqyxt,

ich bin mir nicht ganz sicher, ob ich deine Frage richtig verstanden habe, falls nicht, frag einfach noch einmal nach.

Wie ich es verstanden habe ist, wie man bei einem Wort vorgeht, um zu prüfen, ob das Wort akzeptiert wird oder nicht. Ich nehme mal das erste Beispielwort SS0S110S10S1.

Man beginnt immer mit dem linken Zeichen des Wortes, hier also S (links und rechts stehen noch unendlich viele * aber die sind zunächst nicht relevant).

Bei der Definition T=(...) steht, was der Anfangszustand ist, hier s0. Dann geht man in die Zeile mit dem aktuellen Zustand und nimmt das aktuelle Zeichen (S) für die Spalte. {(s0,S,R)} bedeutet, wir bleiben im Zustand s0, überschreiben das S mit S (ändern also nichts) und gehen ein Zeichen weiter nach rechts, im Beispiel das zweite S (das bedeutet das R. L würde bedeuten nach links zu gehen und bei N bleibt man auf dem aktuellen Zeichen stehen).
Wenn bei einem Zustand mehrere Tupel stehen (wie bei s0-0 zum Beispiel) muss man alle überprüfen bzw.  so lange, bis ein Weg funktioniert. Das Wort wird akzeptiert, wenn alle Zeichen abgearbeitet sind (bzw. genauer: nichts neues mehr kommt, wir also in eine leere Menge davor hatten) und die Turingmaschine in einem Endzustand ist, hier nur s0.

Noch einmal zurück zum Beispiel, beim dritten Zeichen, der 0 haben wir die Möglichkeit in den Zustand s10 oder s11 zu wechseln und wir bleiben auf dem Zeichen stehen und lassen auch die 0 stehen.
1. Fall wie gehen in s11 und fahren fort. Hier kommt es beim 5. Zeichen, der 1 aber zu einem Problem, wir landen in der leeren Menge, ohne in einem Endzustand zu sein, dass heißt, das Wort wird nicht akzeptiert.

2. Fall wenn wir in s10 gehen kommt es zu keinen Problemen und das Wort wird akzeptiert, da wir am Ende auf * stehen (das Zeichen neben der letzten 1) also alles abgearbeitet haben und im letzten Schritt in s0 gewechselt sind.
von uvlwv uvlwv Info-Genie (9.4k Punkte)  
...