Theoretische und technische Informatik - ganz praktisch - Letzte Aktivität 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 :)

Antwort ausgewählt: Keller erst später leeren

Mon, 10 Feb 2020 13:45:28 +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)

Kommentiert: Rückfrage zu der Frage zu Aufgabe 43

Sat, 11 Jan 2020 08:56:54 +0000

Hallo uqysn,

soweit ich das sehen kann, ist Deine Aussage richtig.

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)

Kommentiert: Alternative Lösung

Tue, 18 Jul 2017 07:15:53 +0000

Also bei mir funktioniert es mit der Musterlösung:
@[ID-24668]@

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)

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

Tue, 24 Jan 2017 19:47:29 +0000

Kann anstelle von

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

auch

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

bei sonst gleicher Konfiguration von $\delta$ verwendet werden? Falls nch $\$$ noch Buchstaben kommen würden (also das Wort nicht mehr Teil der Sprache ist) wäre der KA ja im Endzustand aber hätte das Wort nicht abgearbeitet --> nicht akzeptiert oder?

LG

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)

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

Sat, 16 Jan 2016 10:13:16 +0000

Ich habe den Fehler jetzt behoben, siehe hier:
http://www.xwizard.de:8080/Wizz?template=ID-11818

Antwort bearbeitet: Warum wird das leere Wort nicht akzeptiert?

Mon, 04 Jan 2016 08:30:11 +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)

Deterministischer Kellerautomat?

Fri, 24 Oct 2014 07:34:38 +0000

Das Ersetzten von (s0, \$ ,ko)->(s2,ko) anstatt (s0, \$ ,ko)->(s1,ko) macht Sinn.

Ich verstehe aber noch nicht warum (s0,lambda,ko)->(s2,ko) den KA nicht det. macht.

Könnt ihr mir bitte nochmal kurz sagen, wann der KA jetzt det. ist und wann eben nicht det.?

Außerdem ist der Übergang doch auch falsch, weil ich doch immer ein $ im Wort haben muss und dieser Übergang auch das leere Wort zulässt, oder?

Danke & Grüße,

Kai

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)