Theoretische und technische Informatik - ganz praktisch - Letzte Aktivität in KEL-AF

Kommentiert: Wie löse ich Aufgabe 46 unter Benutzung des Kellerspeichers?

Sat, 04 Jan 2020 15:26:00 +0000

Ja, der Algorithmus kann immer angewendet werden, solange nach einem nichtdeterministischen Kellerautomaten gefragt wird. Für die Generierung eines deterministisschen Kellerautomaten kann der Algorithmus nicht verwendet werden.

Viele Grüße,

Sören (Tutor)

Beantwortet: diese Lösung auch möglich?

Fri, 05 Jan 2018 14:21:53 +0000

Hallo,

da sich in deinem Keller, sobald Zustand s3 erreicht wird, nur noch das initiale k0 befindet und dieses nicht gelöscht werden kann (vgl. neues Lehrbuch S.48/49), muss der entsprechende Zustandsübergang wie folgt lauten:

(s3, b, ko) -> (s4, k0)

Die letzte Zeile deiner Zustandsüberführungsfunktion ist überflüssig.

Um dir für die Klausur keine falschen Angewohnheiten anzugewöhnen, solltest du immer darauf achten, den Kellerautomaten immer vollständig anzugeben (dazu gehört das gesamte 6er-Tupel A = (E, K, S, δ, s0 , F) und nicht nur die Zustandsübergangsfunktion.

Ich hoffe ich konnte dir weiterhelfen.

LG Tutor

Kommentiert: Alternativlösung (schon wieder)

Mon, 09 Jan 2017 11:08:33 +0000

Vielen Dank für die schnelle Antwort!

Beantwortet: Alternativlösung?

Wed, 22 Oct 2014 16:47:56 +0000

Stimmt nicht ganz. Die Anzahl der b's vor dem ersten a muss gerade sein (0,2,4,...).

Gruß Jörg (Tutor)

Beantwortet: Alternativlösung ?

Wed, 22 Oct 2014 16:47:19 +0000

Hallo,

meiner Meinung nach sieht das korrekt aus. Allerdings beachte den Hinweis in der Lösung, dass man den Keller nicht zwingend verwenden muss. Dennoch ist es nicht falsch ihn zu verwenden.

Grüße

Simon

Erneut getaggt: Unterscheidung KA det oder ndet ?

Wed, 22 Oct 2014 16:46:19 +0000

wie kann ich denn allgemein erkennen ob ein kellerautomat deterministisch ist und wann nicht deterministisch?

danke

Erneut getaggt: Übergangsrelationen eines ndet KA immer ohne Keller?

Wed, 22 Oct 2014 16:46:04 +0000

Ist es immer so, dass wenn ein nichtdet. KA verlangt wird, dass ,man bei den Übergangsrelationen keinen Keller benutzt?

Ich dachte rechtlin. Gram wäre: P: Nx (T U TN U lamda) oder liege ich falsch?

Erneut getaggt: Frage zu Palindrom in KA

Wed, 22 Oct 2014 16:45:51 +0000

Mit dem Risiko, dass sowas schon mal gefragt wurde.

Bei einem nicht deterministischen KA, zum Beispiel bei einem Palindrom, wo der KA die Mitte richtig "abschätzen" muss. Bei langen Wörtern ist es sehr unwahrscheinlich, dass der Keller richtig "schätzt". Bedeutet das, dass der Keller also meistens das Wort nicht akzeptieren würde und man deshalb den Automaten sehr oft mit dem Wort durchgehen müsste bis er zumindest einmal erkannt wird. Und wenn es ja einmal akzeptiert wird von mehreren Versuchen reicht es ja? Ist das so richtig?

Was aber wenn ich nun ein Palindrom mit Milliarden Stellen habe, lasse den KA ein paar Millionen mal laufen und es wurde immer falsch geschätzt und das Wort wurde durch das falsche "schätzen" kein mal erkannt. Dann geht man fälschlicherweise davon aus, dass das Wort nicht korrekt ist, obwohl es das aber doch ist, richtig?

Beantwortet: Alternativlösung?

Wed, 22 Oct 2014 16:45:02 +0000

Hallo,

das müsste stimmen, denn der einzige Unterschied zu der Musterlösung besteht darin, dass du den Keller mitbenutzst.

Viele Grüße,

Vivian (Tutor)

P.S. Im Übrigen muss dein Keller am Ende nicht unbedingt leer sein (d.h. du könntest auch (s2,b,k0)->(se,bk0) definieren), Hauptsache man kommt am Ende des Wortes in einen Endzustand. Aber das ist nur eine kleine Randbemerkung :)

Kommentiert: Erklärung der Übergänge

Wed, 22 Oct 2014 16:44:21 +0000

Hallo,

lass dich nicht davon verwirren. Hier steht am Ende immer ko, weil unserer Kellerautomat den Keller gar nicht benutzt bzw. braucht. Allerdings gibt es mehrere richtige Lösungen und es ist egal ob du den Keller benutzt oder nicht.

Einfachere Sprachen können ohne den Keller erkannt werden, aber für komplexere Sprache ist sowas nicht mehr möglich. Z.B für die Sprache a^nb^n brauchst du den Keller um die Sprache erkennen zu können, weil du irgendwie zählen muss, wie viele a bzw b vorgekommen sind.

Grüße

Antonio

(Tutor)

Beantwortet: Wieso ist der KA ndet?

Wed, 22 Oct 2014 16:42:31 +0000

Die von dir oben genannten Übergänge sind deterministisch.

Ich denke auch, dass der in der Musterlösung angegebene Kellerautomat deterministisch ist. Ich gebe dir recht, Aufgabenstellung und Lösung passen hier nicht 100-prozentig zusammen.

Allerdings gilt, dass jeder determistische Kellerautomat auch ein nichtdeterministischer Kellerautomat ist, nur eben eine besondere Form davon (Sprachmächtigkeit det. KA ist echte Teilmenge der Sprachmächtigkeit nichtdet. KA)

Melanie (Tutorin)

Beantwortet: Alternativlösung richtig?

Wed, 22 Oct 2014 16:41:28 +0000

Das ist so auch richtig, jedoch könnten Sie (wenn Sie den Keller benutzen wollen, vgl. Hinweis in der Lösung), sogar noch den Zustand s1 sparen, da Sie jetzt sowohl im Zustandswechsel, als auch durch die Benutzung des Kellers die Anzahl der b's speichern. Das ist nicht notwendig (aber auch nicht falsch).

Sie könnten das dann wie folgt verkürzen:

(s0, b, k0) -> (s0, bk0)
(s0, b, b) -> (s0, Lambda)

....

Viele Grüße

Friederike Pfeiffer-Bohnen und Lukas König

Beantwortet: Ist sichergestellt das Wort mit aab endet?

Wed, 22 Oct 2014 16:39:48 +0000

Das Wort aaba wird nicht akzeptiert, weil der KA das Wort komplett abarbeiten muss, um zu akzeptieren (im Ggs. zur TM).

Viele Grüße

Lukas König

Kommentiert: Alternativlösung richtig?

Wed, 22 Oct 2014 16:32:44 +0000

Hallo,

durch den Nichtdeterminismus machst du dir das Leben ein wenig schwer, so kann es bei deinem KA passieren, dass das leere Wort akzeptiert wird. Die Wörter sollen allerdings alle auf aab enden. Wenn du aber den ersten Übergang weglässt, dann müsste der Rest stimmen.

Viele Grüße,

Vivian (Tutor)

Beantwortet: Einige Nachfragen

Wed, 22 Oct 2014 16:31:05 +0000

zu 1. Dass es hier eine rechtslineare Grammatik gibt und somit einen Kellerautomaten, der den Keller nicht nutzt, das müssen Sie hier nicht erkennen. Es war nur ein nichtdeterministischer Kellerautomat gefordert. Wenn Sie diesen anders (z.B. mit Verwendung des Kellers) konstruieren, und er richtig ist und zu den Vorgaben der Aufgabenstellung passt, dann ist das ja auch in Ordnung.

zu 2. Ich gehe davon aus, dass Sie hier überprüfen wollen, ob ein Wort zu einer Sprache gehört, d.h. ob dieses von dem Kellerautomat akzeptiert wird (Akzeptor)? Ob ein Wort zu der gegebenen Sprache gehört oder nicht sieht man daran, ob der Kellerautomat nach Abarbeitung des Wortes in einem Endzustand ist oder nicht. ("Zeichen aus dem Keller löschen" hilft Ihnen beispielsweise die Anzahl von Zeichen zu zählen, vgl. a^nb^n, hilft Ihnen aber nicht zu erkennen, ob ein Wort zu der Sprache gehört oder nicht.)

zu 3. sobald hier das erste a kommt, sollten Sie den Zustand wechseln, um zu gewährleisten, dass nach dem a nur noch genau ein a (dann wäre im Keller genau ein a, welches wieder gelöscht werden könnte) und ein b (der Keller enthielte nur k0) kommt.

zu 4. dieses Kodieren der geraden / ungeraden Anzahl an b's können Sie, wie bereits beschrieben, auch mit Hilfe des Kellers erreichen.

Freundliche Grüße
Friederike Pfeiffer