Theoretische und technische Informatik - ganz praktisch - Letzte Fragen & Antworten in KEL-AF

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

Fri, 03 Jan 2020 14:31:43 +0000

Hallo,

Streng genommen muss der Keller bei uns nicht leer sein, damit das Wort erkannt wird. Laut Definition ist es ausreichend, wenn das Wort abgearbeitet ist und wir in einem Endzustand sind.
Es macht jedoch oft Sinn mit einem leeren Keller zu enden, da wir hier Informationen „speichern“. Um z.B. zu garantieren, dass genau zwei a’s eingelesen wurden, schreiben wir diese wenn sie vor kommen in den Keller und bauen unsere Übergänge so auf, dass wir diese nur genau zweimal rauslöschen können (Nicht mehr und nicht weniger).
In deinem Beispiel fehlt dieser Mechanismus und der Kellerautomat würde z.B. auch das Wort aaaab akzeptieren (das nicht Teil der Sprache ist).

(so,aaaab,ko) -> (s1,aaab,ak0) -> (s1,aab,aak0) -> (s1,ab,aaak0) -> (s1,b,aaaak0) -> (se,lambda,aaaak0)

Im Folgenden findest du ein Beispiel, das den Keller verwenden würde und funktioniert:

Endzustand F = {se}

(s0, b, k0) -> (s0, bk0)
(s0, b, b) -> (s0, Lambda)
(s0, a, k0) -> (s0, ak0)
(s0, a, a ) -> (s2, Lambda)
(s2, b, k0) -> (se, k0)

Die ersten beiden Übergänge stellen sicher, dass nur eine gerade Anzahl an b’s eingelesen werden kann und durch den Wechsel in s2 (im 4.Übergang), nachdem das zweite a eingelesen wird ist sichergestellt, dass im Anschluss nur noch genau ein b kommen kann. Dies ist die einzige Möglichkeit ausgehend von s2 in den Endzustand zu kommen.

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

Beantwortet: Alternativlösung (schon wieder)

Mon, 09 Jan 2017 10:22:38 +0000

Hallo ubesx,

ja der Automat scheint korrekt zu sein. An sich brauchst du beispielsweise bei den beiden folgenden Übergängen gar nichts in den Keller zu schreiben, so wie es auch in der Musterlösung gemacht wurde, aber es ist natürlich auch nicht falsch. Der reine Übergang in einen anderen Zustand und das Zurückkehren in den ursprünglichen Zustand beim zweiten b würden reichen.
so,b,ko --> s2,bko
s2,b,b --> so,ko (hier müsste statt ko lambda stehen, da du das b wieder aus dem Keller „löschen“ möchtest)

Also:
so,b,ko --> s2,ko
s2,b,ko --> so, ko

Dadurch, dass du in dem anderen Fall( falls direkt ein a kommt) ein a in den Keller schreibst, sparst du dir hier natürlich einen Zustand, was man so machen kann.

Wie im Tutorium behandelt ist jeder deterministische Automat gleichzeitigt auch nichtdeterministisch.
--> Demnach ist hier gewährleistet, dass der Automat auch nichtdeterministisch ist.

Grüße, Sören (Tutor)

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

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 :)

Beantwortet: Erklärung der Übergänge

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

Hallo,

hier ist eine grobe Beschreibung der Idee:

Zuerst einmal wissen wir, dass die Wörter aus der Sprache eine gerade Anzahl an b's haben und immer auf aab enden müssen.

s0 = Startzustand, und Zustand, in dem die Anzahl der b's gerade ist

s1 = Zustand, in dem die Anzahl der b's ungerade ist

s2 = Zustand, der nach dem ersten a schaut, ob das zweite a folgt

s3 = Zustand, der nach dem zweiten a schaut, ob ein b folgt

se = Endzustand

Wenn wir in s0 starten und ein b einlesen, dann haben wir eine ungerade Anzahl an b's, also rüber in s1. Beim nächsten b in s1 sind wir wieder im geraden Bereich, also wechseln wir zurück in s0. Und so kann man dann hin und her wechseln solange wir weiter b's einlesen.

Wenn wir in s0 sind und ein a einlesen, dann wissen wir, dass wir uns damit schon im Endteil "aab" des Wortes befinden müssen. Also wird der Zustand gewechselt in s2, und dort an wird dann weiter geprüft, ob der weitere Verlauf des Wortes wirklich "aab" entspricht.

Hoffe, das konnte dir einen Überblick verschaffen :)

Viele Grüße,

Vivian (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

Beantwortet: Frage zu Palindrom in KA

Wed, 22 Oct 2014 16:38:35 +0000

Woher kommen denn diese (nicht ganz korrekten) Formulierungen? Ein KA kann nicht schätzen.

Bei einem nichtdet. KA sprechen wir davon, dass er "raten" kann - das ist allerdings etwas salopp formuliert und bedeutet nicht schätzen! Ein nichtdet. Automat (also sowohl KA als auch EA, TM, ...) kann beliebig viele Konfigurationen auf einmal betrachten, weil er ja aus einem Zustand in beliebig viele Folgezustände übergehen kann. Er kann also in n Berechnungsschritten alle nach n Schritten erreichbaren Konfigurationen betrachten. Das bedeutet, dass er aus den viele möglichen Konfigurationsfolgen, die vom Startzustand aus existieren, die richtige (also die, die zu einer akzeptierenden Konfiguration führt) aussuchen kann. In diesem Sinn kann er "raten" - er rät aber immer richtig, solange es eine akzeptierende Konfigurationsfolge gibt. Auf diese Weise kann ein nichtdet. KA diejenige Konfigurationenfolge erraten, die gerade die Mitte eines potentiellen Palindorms trifft (und zwar für Palindrome beliebiger Länge!). (Es ist natürlich zu beachten, das Nichtdeterminismus ein mathematisches Konstrukt ist - so einen ratenden Automaten können wir in Wirklichkeit nicht bauen; in der Wirklichkeit sind wir immer deterministisch.)

Ein det. KA kann die Mitte eines Palindorms nicht finden und auch nicht "abschätzen".

Viele Grüße

Lukas König

Beantwortet: Übergangsrelationen eines ndet KA immer ohne Keller?

Wed, 22 Oct 2014 16:36:37 +0000

Hallo, hier noch ein Nachtrag zu obigen Fragen:

"Ist es immer so, dass wenn ein nichtdet. KA verlangt wird, dass ,man bei den Übergangsrelationen keinen Keller benutzt?"
- Nein, das eine hat mit dem anderen nichts zu tun.

"Ich dachte rechtlin. Gram wäre: P: Nx (T U TN U lamda) oder liege ich falsch?"
- Hier liegen Sie richtig, das ist eine rechtslineare Grammati.

Viele Grüße
Friederike Pfeiffer

Beantwortet: Unterscheidung KA det oder ndet ?

Wed, 22 Oct 2014 16:34:53 +0000

1) Ein deterministischer Automat ist auch immer ein nicht deterministischer Automat. Daher kann man hier auch einen deterministischen Automaten angeben.

2) Bei der Ableitung von Testworten wählt man die Übergänge so, dass das Testwort akzeptiert wird (falls dies möglich ist).

Zum Unterschied: Bei einem det Automaten ist in jedem Zustand für jede Eingabe völlig klar, was der nächste Zustand sein wird. Bei einem ndet Automaten nicht, da es mehrere Möglichkeiten geben kann.

Sven (Tutor)

Beantwortet: Alternativlösung richtig?

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

Die Idee ist hier richtig, jedoch stimmen bei Ihnen einige Zustandsübergänge nicht. Ich gehe davon aus, dass bei Ihnen se Endzustand ist? Durch den lambda-Übergang machen Sie Ihren Automaten im übrigen nicht-deterministisch. Sie lesen zwei b's und bleiben dann in s0 und der Keller ist leer. Dann könnten Sie auch von hier direkt in se wechseln, was Sie aber nicht dürfen, da das Wort auf aab enden soll. Demnach müssen Sie hier irgendwo den Zustand wechslen, um nicht über den lambda-Übergang in den Endzustand zu gelangen (so wie Sie das auch mit den a's machen). Der Rest sieht aber gut aus.

Viele Grüße
Friederike Pfeiffer

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