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

Beantwortet: Wann akzeptiert ein Kellerautomat das leere Wort?

Thu, 18 Mar 2021 10:37:54 +0000

Danke euch! Das hilft mir sehr :)

Beantwortet: Keller erst später leeren

Mon, 10 Feb 2020 13:42:18 +0000

Ich glaube mit deinem ersten Satz liegst du falsch, denn auf Folie V9-57 steht, dass ein Wort akzeptiert wird, wenn das Wort vollständig abgearbeitet ist und der KA sich in einem Endzustand befindet. Der Keller muss meiner Meinung nach nicht leer sein.

Beantwortet: Kellerautomat Endzustand

Sat, 11 Jan 2020 09:23:27 +0000

Hallo uqysn,

Deine Aussage stimmt. Für das Wort "$a": der Automat bricht nach der Eingabe "$" in Endzustand s2 ab, trotzdem wird das Wort nicht akzeptiert.

Siehe Vorslesungsfolie V9-51:

Ein Wort wird akzeptiert, falls nach dem Halten:

LK steht rechts von w (Wort ist vollständig verarbeitet)

und

KA im Endzustand

Viele Grüße,

Runxi (Tutorin)

Beantwortet: Rückfrage zu der Frage zu Aufgabe 43

Fri, 10 Jan 2020 20:27:29 +0000

Hallo uipmv,

deine Aussage über die Akzeptanz stimmt. In dem genannten Beispiel wird das Wort $a dementsprechend nicht akzeptiert.

Viele Grüße,

Runxi (Tutorin)

Beantwortet: Verständnisproblem

Mon, 06 Jan 2020 15:02:03 +0000

Hallo uxgzf,

wie uqysn schon festgestellt hat, wir bei dem Zustandsübergang von (s0, $, a) → (s1,a) nur der Zustand gewechselt (von s0 in s1). Dies ist nötig, da nach dem $ überprüft werden muss, ob tatsächlich eine Spiegelung des Abschnitts vor dem $ vorliegt.

Die Sprache L = { w ∈ {a,b,$} | w = u$u', u ∈ {a,b}} besteht ja gerade aus Wörtern, deren Abschnitt u nach der Mitte des Wortes (gekennzeichnet durch $) nochmals gespiegelt als u' geschrieben wird.

Viele Grüße,

Dominik (Tutor)

Beantwortet: Alternative Lösung

Mon, 17 Jul 2017 14:09:18 +0000

Schauen Sie mal, wenn $s_e$ Ihr Endzustand sein soll, dann ergibt sich im XWizard dieser Automat, der auf die Eingabe $abaDaba$ (mit $D$ statt Dollar) leider nicht akzeptiert. Sie können im XWizard ja mal damit herumspielen, bis es funktioniert.

(Klicken Sie auf die Zustände im Bild, um zu animieren.)

@[ID-24607]@

Beantwortet: Alternativ

Fri, 27 Jan 2017 01:58:36 +0000

Man kann $(s_0, \$, k_0) \rightarrow (s_2,k_0)$ statt $(s_0, \$, k_0) \rightarrow (s_1,k_0)$ schreiben.

$(s_1, \lambda, k_0) \rightarrow (s_2,k_0)$ darf jedoch nicht weggelassen werden.

Viele Grüße

Philipp (Tutor)

Beantwortet: Ist folgender Übergang für $\delta(s_0, \$, k_0)$ auch möglich?

Tue, 24 Jan 2017 15:16:27 +0000

Ja, man kann

$\delta(s_0, \$ , k_0) = (s_1, k_0)$ durch $\delta (s_0, \$ , k_0) = (s_2, k_0)$

ersetzen und es wird weiterhin dieselbe Sprache akzeptiert.

Viele Grüße

Philipp (Tutor)

Beantwortet: Stern w aus der Menge {a,b,$}*

Sat, 06 Feb 2016 16:17:11 +0000

Hallo,

zunächst einmal bedeutet w Element {a, b, \$}*, dass die Wörter der Sprache aus eben diesen drei Zeichen bestehen, und zwar zunächst beliebig viele davon beliebig aufeinander folgend. Hier wäre also das leere Wort enthalten.

Die Einschränkung nach dem "|" macht dann jedoch weitere Vorgaben für das Aussehen der Wörter: Diese müssen symmetrisch um das \$ aufgebaut sein, u' ist u nur "rückwärts geschrieben". u und u' bestehen dabei wieder aus a's und b's und können auch kein Zeichen enthalten.

Das \$ ist jedoch für jedes Wort der Sprache zwingend, womit das leere Wort kein Teil der Sprache ist.

Ganz simpel gesprochen beinhaltet die Sprache übrigens alle Wörter, die um das $-Zeichen herum ein Palindrom bilden.

Ich hoffe, dass damit die Definition der Sprache klarer wird und der Startzustand kein Endzustand sein kann.

Viele Grüße

Max (Tutor)

Beantwortet: (fehlende) Übergänge in s1

Thu, 04 Feb 2016 14:50:48 +0000

Hallo uyejk,

mit den vorgeschlagenen Übergängen würde der Kellerautomat nicht mehr die angegebene Sprache erkennen. Er funktioniert ja gerade so, dass er bis zum $ \$ $ -Zeichen alle Zeichen speichert, und nach dem $ \$ $ immer vergleicht, ob das oberste Kellerzeichen dem gerade gelesenen Zeichen entspricht - falls ja, wird das oberste Kellerzeichen gelöscht, falls nein hält er an und akzeptiert das Wort nicht.

Viele Grüße

Jonas (Tutor)

Beantwortet: Erkennt der KA in der Lösung nicht eine größere Sprache als verlangt?

Thu, 14 Jan 2016 12:15:37 +0000

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.

Beantwortet: Warum wird das leere Wort nicht akzeptiert?

Sat, 02 Jan 2016 13:00:12 +0000

Hey ukdxs,

zunächst mal zu deiner ersten Frage: Bei der Sprachdefinition ist es extrem wichtig, dass du diese immer komplett betrachtest und nicht anhand vom * bzw. + im ersten Teil schon davon ausgehst, dass das leere Wort in der Sprache ist bzw. nicht. Im linken Teil werden die Zeichen definiert aus denen die Wörter bestehen (hier a,b,\$) und zunächst das leere Wort eingeschlossen. Für sämtliche Wörter aus dieser Menge muss die Bedingung die folgt jedoch noch zutreffen (Palindrom mit Dollar-Zeichen in der Mitte). Nur dann sind sie auch Wörter der Sprache. Da dies für das leere Wort nicht zutrifft, gehört es auch nicht zu der Sprache.

Nun zu deinem Automaten:
Die Zustandsüberführungsfunktionen für s2 sind nicht korrekt. Sobald das erste Zeichen nach dem Dollar-Zeichen mit dem letzten Zeichen vor dem Dollar-Zeichen übereinstimmt, springt dein Automat in s3 ohne restlichen Zeichen zu überprüfen. Man darf hier also nicht direkt in den Endzustand springen.
Zudem ist deine letzte Funktion einer Art Endlosschleife für den Automaten. Ist er in s3 und k0 im Keller, bleibt er in s3 und änder nicht im Keller. Und die Funktion wird wieder ausgeführt. Daher wird bei der Musterlösung ein weiterer Zustand als Endzustand genutzt. In diesen könnte man, meiner Meinung nach, wenn der Automat in s1 ist, \$ eingelesen wird und k0 im Keller steht auch direkt springen.

Ich hoffe ich konnte deine Fragen beantworten!

Viele Grüße
Ashvin

Beantwortet: Zustandswechsel

Fri, 24 Oct 2014 11:00:15 +0000

Hallo,

in s0 wird da Wort vor dem Dollar abgearbeitet und sobald das Dollarzeichen kommt wechseln wir in s1, in diesem zustand wollen wir den hinteren Teil überprüfen. Konnte das Wort vollständig udn korrekt abgearbeitet werden, d.h. wir befinden uns in Zustand s1 und Arbeitsband ist leer, so wechseln wir in den Endzustand. So sind die Zustände zu verstehen.

Bei den anderen Aufgaben musste man oft sofort in einen anderen Zustand wechseln, da der Kellerautomat

1) deterministisch und zusätzlich

2) das leere Wort

beinhaltet. 2) ist hier nicht der Fall. Dieses Problem haben wir bei deterministischen Automaten, da wir in s0 am Anfang keinen lambda-übergang definieren dürfen. Schau dir diese Aufgaben am Besten nochmal an.

Gruß,

Adam (Tutor)

Beantwortet: Übergang

Fri, 24 Oct 2014 07:36:52 +0000

Sobald eine dieser Situationen eintritt, die du aufgelistet hast, ist das Wort nicht mehr Teil der Sprache. Der Kellerautomat erkennt in diesem Fall, dass das Wort noch nicht abgearbeitet wurde oder dass er sich nicht in einem Endzustand befindet (oder beides). Daraus schließt er automatisch, dass die Eingabe kein Wort der vorgegebenen Sprache sein kann. Ein "Sackgassenzustand", wie er bei den endlichen Automaten vorkam, ist hier nicht nötig.

Gruß

Lukas (Tutor)

Beantwortet: Deterministischer Kellerautomat?

Fri, 24 Oct 2014 07:35:00 +0000

Ein (Keller-)Automat ist immer solange deterministisch, wie es für jede mögliche Konfiguration nur einen einzigen möglichen Folgezustand gibt. Wenn man einen Lambda-Übergang in einem Kellerautomaten hat, dann kann dieser immer genommen werden, unabhängig vom aktuell gelesenen Eingabezeichen. Das heißt, dass so ein Automat genau dann deterministisch ist, wenn es für dasselbe Kellersymbol (wie beim Lambda-Übergang) keinen anderen Übergang mit einem der Eingabesymbole a gibt. Denn sonst hätte man in der Situation, dass gerade a gelesen wird, zwei Möglichkeiten: den Übergang mit a nehmen oder den mit Lambda.

Grüße

Lukas König

Beantwortet: Richtigkeit anhand Testwort

Fri, 24 Oct 2014 07:27:57 +0000

Zu 1) Nein, da kannst du leider nicht sicher sein. Du könntest ja auch einfach Glück haben und mit deinem fehlerbehafteten KA das Testwort erkennen.

Zu 2) Es gibt oft viele Möglichkeiten, eine richtigen KA zu definieren. Am besten man versucht auch alle möglichen Spezialfälle zu überdenken und in Produktionen zu erfassen. Bsp: leeres Wort, a^m b^n c^k mit m = n+k : n oder k können null sein etc.

Viele Grüße,

Sven (Tutor)