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

1 Pluspunkt 0 Minuspunkte
114 Aufrufe

Hi,

ab dem Schritt mit dem # verstehe ich den Kellerautomaten leider nicht mehr... kann mir jemand kurz erklären, was man sich bei den darauf folgenden Zeilen denken muss? Danke :)

 

in 2013-B-02 von uafjv uafjv Tutor(in) (168k Punkte)  

2 Antworten

1 Pluspunkt 0 Minuspunkte

Ab dem # kommt das zweite Teilwort v=a^l b^n a^m

Im Keller ist bereits das erste Teilwort u=a^i b^n a^k.

Jetzt kommen die ersten a's von v und löschen jeweils die letzten a's von u aus dem Keller. Aus der Aufgabenstellung weiß man dass l>k gelten muss. Deshalb müssen auch a's verarbeitet werden wenn bereits ein b als oberstes Kellerzeichen ausgegeben wird.

Dann werden die b's von u mit den b's von v rausgelöscht (genau gleich viele). Und am Schluss noch die letzten a's von v mit den ersten a's von u (wie oben).

Ich hoffe das war hilfreich. Wenn nicht noch mal etwas konkreter nachfragen.

Gruß Jörg (Tutor)

 

von uafjv uafjv Tutor(in) (168k Punkte)  
1 Pluspunkt 1 Minuspunkt

Hallo,

Ich machs mal komplett: Am Anfang schreibt man einfach alle Zeichen des ersten Teilwortes (u) in den Keller hinein. Der Übergang von s0 zu s1 erfolgt dabei, nachdem man nach dem b wieder ein a gelesen hat. Dies ist notwendig damit der Automat stoppt, wenn zB abab gelesen wird. Soweit ist es dir ja klar.

Das Trennzeichen wird dann nicht in den Keller geschrieben. Da alle Zeichen mindestens einmal enthalten sein sollen, weiß man, dass # auf jeden Fall gelesen wird, wenn ein a oben im Keller steht. (s1, #, a ) => (s2,a) heißt dann dementsprechend, dass der Keller nicht verändert wird und das oberste Zeichen einfach stehen bleibt (hier eben a). Außerdem erfolgt ein Zustandsübergang in s2, da wir uns nun im rechten Teilwort befinden (v).

Nun sollen die Wörter aus u nach dem b weniger a's haben, als v vor dem b. Für den Automaten heißt dies, dass wir für jedes a, welches wir nun lesen, die a's aus dem Keller löschen. (Zusätzliche Erklärung: Die a's, die oben im Keller stehen, sind ja die a's die in u nach dem b folgen. Hierzu einfach mal den Keller hinschreiben!)

Da nun ja die Zahl der a's, die wir im zweiten Teilwort gerade lesen echt größer sein soll, müssen wir ein b oben im Keller stehen haben UND noch a vom Eingabewort lesen. (unser Keller enthält also zu diesem Zeitpunkt (a^i b)). Wenn wir also in s2 sind und noch weiter a's von der Eingabe lesen und b im Keller steht, so machen wir mit den a's einfach nichts und lassen b oben stehen, außerdem wird in Zusant s3 gewechselt.

Wenn nun b (von der Eingabe) auf b (vom Keller) gelesen wird, so wechseln wir in s4, denn nun werden die b's gelöscht. Die Anzahl soll in Wörtern der Sprache ja für beide Teilwörter gleich lang sein. Somit müssen wir a auf a lesen, wenn alle b's im Keller und im Eingabewort abgearbeitet sind.

Nun sollen wieder mehr a's im rechten Teilwort sein, als im linken. Wir löschen also solange die a's, bis der Keller leer ist (k0 steht oben). Wird dann k0 im Keller gelesen, wird in den Endzustand (s5) gewechselt und es können noch beliebig viele weitere a's kommen.

Sooooo, ich hoffe das reicht dir als Erklärung ;)

Viele Grüße,

Julian (Tutor)

 

von uafjv uafjv Tutor(in) (168k Punkte)  
0 0
Eine allgemeine Frage dazu, da ich in meinem ersten Entwurf den Übergang von s0 auf s1 nicht hatte: Sind "zu viele" Zustände falsch - beispielsweise in dieser Aufgabe nach jedem neuen Buchstaben ein neuen Zustand? So könnte man diverse Eventualitäten abfangen. Mit Sicherheit ist es nicht die schönste Lösung.

LG & danke! :)
...