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

3 Pluspunkte 0 Minuspunkte
252 Aufrufe

Hallo,

ich habe mir gerade die Lösung zur Aufgabe 43 angesehen und mich gefragt, ob die akzeptierte Sprache nicht über die geforderte hinausgeht, da ich glaube, auch Wörter der Form v$v'ab bzw. das geforderte Palindrom und anschließend eine beliebige Folge von Zeichen, da gemäß der Lösung der Zustandsübergang von (s1, λ, k0) (s2, k0in den Endzustand s2 führt, ungeachtet, was sonst noch kommt.

Ich habe den KA im XWizard simuliert und dort wird bei Eingabe von v$v'aab das Wort akzeptiert. In der Zusammenfassung des Übungsbuches steht jedoch, dass das Eingabewort auch vollständig abgearbeitet sein muss, damit es akzeptiert wird. In diesem Fall würde die Lösung stimmen, aber der XWizard mehr akzeptieren. Ist die Lösung nun richtig und der XWizard stimmt nicht oder andersherum (oder sehe ich den Wald vor lauter Bäumen nicht mehr :)).

Sollte die Lösung stimmen, wäre meine Frage noch, ob die Überführung (s0, $, k0) (s1, k0nicht auch direkt in se gehen könnte, da im Falle eines Restwortes dieses ja dann nicht akzeptieren werden würde.

 

Ich hoffe, ich habe das jetzt nicht zu kompliziert formuliert.

in KEL-AC von udeqy udeqy Lernwillige(r) (950 Punkte)  
0 0
Können Sie bitte mal das Script posten, das den Fehler verursachen soll?
0 0
Da ich mein Skript nicht mehr hatte, habe ich das Skript aus der Lösung kopiert und als Beispielwort $w=abbaDabbaabbb$ gewählt, was ja laut Definition nicht u$u' ist., Wenn ich nun auf "Zeige Berechnungsschritte (Latex)" klicke, wird mir angezeigt, dass das Wort akzeptiert wird, obwohl noch ein Restwort verfügbar ist und somit das Wort kein Palindrom ist.

pda:
(s1, a, a) => (s1, lambda);
(s0, D, k) => (s1, k);
(s0, D, a) => (s1, a);
(s0, b, b) => (s0, bb);
(s0, a, b) => (s0, ab);
(s0, b, a) => (s0, ba);
(s1, b, b) => (s1, lambda);
(s0, a, a) => (s0, aa);
(s1, lambda, k) => (s2, k);
(s0, D, b) => (s1, b);
(s0, b, k) => (s0, bk);
(s0, a, k) => (s0, ak);
--declarations--
e=#n#;
s0=s0;
F=s2;
kSymb=k;
inputs=abbaDabbaabbb;
simSteps=11;
maxNondetCalcDepth=12
--declarations-end--
0 0
Vielen Dank für den Hinweis! Sie haben recht, der XWizard hat hier einen Fehler. Das Wort dürfte nicht akzeptiert werden.
0 0
Ich habe den Fehler jetzt behoben, siehe hier:
http://www.xwizard.de:8080/Wizz?template=ID-11818

2 Antworten

0 Pluspunkte 0 Minuspunkte

Hallo udeqy,

ich hoffe ich habe deine Frage richtig verstanden.

Der Zustandsübergang (s1, λ, k0) → (s2, k0) ist nur möglich wenn das Wort vollständig abgearbeitet (nur dann wird ein  λ gelesen) und der Keller leer ist (Kellerzeichen k0).

EDIT : Der Zustandsübergang (s1, λ, k0) → (s2, k0) ist auch möglich, wenn noch ein Restwort abzuarbeiten ist! Damit ein Kellerautomat ein Wort akzeptiert muss der Automat allerdings in einem Endzustand sein UND das Wort vollständig abgearbeitet sein (siehe auch Folie 3-5).

Der Fall (s0, $, k0) (s1, k0) ist notwendig, wenn u´ und v´ leer sind, da in diesem Fall das Wort nur aus einem $ besteht, aber trotzdem Teil der Sprache ist.

Du kannst ja mal dein X-Wizard Skript hier posten, damit wir es nachvollziehen können.

Viele Grüße

Gregor (Tutor)

von uhdzw uhdzw Tutor(in) (102k Punkte)  
Bearbeitet von uhdzw uhdzw
0 0
Danke für die schnelle und ausführliche Antwort.

Wenn ich es in der Vorlesung richtig verstanden habe, muss bei einem Übergang der Form (s1, λ, k0) → (s2, k0)  das Eingabewort nicht komplett abgearbeitet sein, sondern es wird einfach das aktuelle Zeichen ignoriert und nach dem Übergang dieses wieder aufgenommen. Falls dem nicht so sei, habe ich meinen Denkfehler gefunden.
0 0
Ich habe eben noch mal in den Folien zum Kellerautomatennachgeschaut. Du hast recht, der Übergang (s1, λ, k0) → (s2, k0) ist nach der Definition möglich, auch wenn rechts noch ein Restwort steht. Allerdings muss das Wort komplett abgearbeitet sein, damit der Kellerautomat das Wort akzeptiert (siehe Folie 3-5).

Viele Grüße
Gregor (Tutor)
0 Pluspunkte 0 Minuspunkte

Aha, jetzt verstehe ich, glaube ich, wo das Problem liegt! Ich muss mir das nachher noch genauer anschauen, aber das Problem ist ziemlich sicher, dass das Dollarzeichen in Latex ein reserviertes Zeichen ist. Deshalb läuft vermutlich alles schief. Hier auf der Seite übrigens auch, deshalb habe ich Ihr Skript abgeändert, sodass statt dem Dollarzeichen ein D steht.

Versuchen Sie mal bitte das veränderte Skript im XWizard - bleibt das Problem bestehen?

EDIT: Nein, das war es nicht, der XWizard behauptet tatsächlich, dass das Wort akzeptiert wird. Das ist ein Programmier-Fehler! Ich werde versuchen, das baldmöglichst zu beheben.

von Dozent (10.1m Punkte)  
...