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
54 Aufrufe
Hallo zusammen,

ich habe da noch einmal eine Frage zu den Übergängen in s1.

Warum werden nur die Übergänge (s1,a,a) und (s1,b,b) betrachtet? Es kann doch aber auch sein, dass das oberste Zeichen des Kellers a ist, wenn b auf dem Band gelesen wird bzw. b das oberste Zeichen und a auf dem Band, dann müssten die Übergänge  (s1,a,b) => (s1,lamda) und (s1.b,a) => (s1, lamda ) doch auch definiert werrden?

Dankeschön!
in KEL-AC von uyejk uyejk Lernwillige(r) (760 Punkte)  
Bearbeitet von uyejk uyejk

2 Antworten

0 Pluspunkte 0 Minuspunkte
Hallo uyejk!

Nein, die von dir oben beschriebenen Fälle (a oberstes Kellerzeichen, b auf Band oder umgekehrt) sollen im Zustand s1 gerade nicht möglich sein und sind deshalb nicht als Übergänge definiert.

Wenn du sich der Kellerautomat im Zustand s1 befindet bedeutet das, dass der erste Wortteil u und das Trennzeichen $ bereits gelesen wurden und nun soll überprüft werden, ob der nun folgende Teil u' gerade der Umkehrung von u entspricht. Die Buchstaben (a und b) von u wurden zuvor (im Zustand s0) auf den Keller geschrieben und zwar nacheinander, d.h. dass das erste Zeichen von u ganz unten im Keller steht und das letzte ganz oben. Wenn du nun also überprüfen willst, ob u' gerade der Umkehrung von u entspricht, vergleichst du also das auf dem Band gelesene Zeichen (=erstes Zeichen von u') mit dem obersten Kellerzeichen (=letztes Zeichen von u). Wenn beide übereinstimmen (a=a oder b=b), dann löschst du das oberste Kellerzeichen und der Kellerautomat liest das nächste Zeichen auf dem Einganeband. Falls die beiden nicht übereinstimmen, dann ist u' nicht die Umkehrung von u und der Kellerautomat bricht somit hier ab (d.h. kein Übergang definiert), da das eingegebene Wort die Sprachdefinition u$u' verletzt.

Ich hoffe, das hilft dir weiter!

Viele Grüße,

Janine (Tutorin)
von uedqi uedqi Tutor(in) (109k Punkte)  
0 Pluspunkte 0 Minuspunkte
Hallo uyejk,

mit den vorgeschlagenen Übergängen würde der Kellerautomat nicht mehr die angegebene Sprache erkennen. Er funktioniert ja gerade so, dass er bis zum $ \$ $ -Zeichen alle Zeichen speichert, und nach dem $ \$ $ immer vergleicht, ob das oberste Kellerzeichen dem gerade gelesenen Zeichen entspricht - falls ja, wird das oberste Kellerzeichen gelöscht, falls nein hält er an und akzeptiert das Wort nicht.

Viele Grüße

Jonas (Tutor)
von ufdzo ufdzo Tutor(in) (103k Punkte)  
...