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 1 Minuspunkt
228 Aufrufe

Hallo,

könnte jemand freundlicherweiße das Vorgehen bei dieser Aufgabe erläutern?

Mir ist nicht so ganz klar wie ich bei Aufgaben diesen Typs herangehen muss, um den Kellerautomaten anzugeben. Insbesondere die ganzen Übergänge die man definiert.

Vielen Dank!

 

in AU-2-3 von uafjv uafjv Tutor(in) (168k Punkte)  

1 Eine Antwort

0 Pluspunkte 0 Minuspunkte

Hallo,

ein genaues "Rezept" gibt es bei solchen Aufgaben nicht, vieles kommt erst mit der Zeit, wenn man viele Aufgaben gesehen hat. Eventuell kann eine Skizze des Kellers ganz hilfreich sein.

Die Herangehensweise in dieser Aufgabe ist so ähnlich wie in der VL (bzw. auf der Einführungsfolie im Tut), dort wurde ein KA konstruiert für Wörter der Form (a^n)(b^n). Dort hat man zuerst alle a's in den Keller geschrieben und anschließend für jedes b das man eingelesen hat, ein a aus dem Keller gestrichen. Wenn der Keller am Ende leer und das Wort zuende war, dann wusste man, dass das Wort genausoviele a's wie b's hatte.


Der einzige Unterschied in dieser Aufgabe ist, dass die 0er und 1er in beliebiger Reihenfolge auftauchen können. Das heißt, dass das, was man in den Keller reinschreibt, abhängt von dem Zeichen das man in s0 einliest.

Beim Definieren der Übergänge kannst du dir zuerst überlegen, ob lambda in der Sprache liegt (d.h. s0 = Endzustand = gleich viele 1er & 0er). Danach kannst du schrittweise parallel zu einer Skizze überlegen, wie du deine Übergänge definieren willst.


Bsp.: 0110. Wenn du eine 0 reinmalst, dann solltest du in s1 wechseln, da sonst das Wort 0 auch akzeptiert werden würde. Danach bietet es sich an, die 0 zu streichen wenn eine 1 folgt. Dann ist der Keller leer und im bisherigen Teilwort gab es genauso viele 0er wie 1er. Deswegen wechselst du zurück in s0 mit (s1,lambda,k0) -> (s0,k0). So kannst du dann weiter verfahren und auf eine Lösung kommen :)

Viele Grüße,

Vivian (Tutor)

 

von uafjv uafjv Tutor(in) (168k Punkte)  
...