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

Beantwortet: Wieso ist der KA bei einem Zustandsübergang wie diesem nichtdeterministisch?

Sun, 04 Feb 2018 11:19:25 +0000

Hallo,

sie sind nur dann nichtdeterministisch wenn es neben dem Lambda-Übergang noch einen anderen Übergang mit gleicher Zustand-Keller-Kombination gibt.

Mit freundlichen Grüßen

Laurin (Tutor)

Beantwortet: fehlender Zustand mit drin

Tue, 18 Jul 2017 06:41:22 +0000

Na ja, Sie können zum Beispiel Ihren neuen Übergang zum Skript aus dem verlinkten Post (das übrigens falsch war, ich habe es korrigiert) hinzufügen und sich dann die Berechnung für ein Beispielwort anschauen. Im Fall des Wortes $ababbaba$ funktioniert das bspw. wie unten angegeben (am Ende wird akzeptiert, also passt es in diesem Fall).

Allerdings ist das natürlich kein Beweis, dass es für alle Wörter der verlangten Sprache funktioniert. In vielen Fällen sehen Sie aber schnell, wenn etwas schiefläuft und woran es liegt. Sie können auch andere Wörter unter $inputs=...;$ angeben und sich die entsprechenden Berechnungen anschauen (dafür müssen Sie auf den Link zur XWizard-Seite klicken, das geht nicht direkt auf dieser Seite). Zum Animieren klicken Sie am besten in die Zustände des Automaten.

@[ID-24652]@

Beantwortet: Lambda Übergang, KA nicht det

Thu, 26 Jan 2017 19:47:18 +0000

Wichtig beim Determinismus ist es, dass wenn ein Lamda-Übergang definiert ist, nicht auch noch ein weiterer Übergang für das gleiche Kellerzeichen und den gleichen Zustand definiert sein darf.

Beantwortet: Definition neuer Zustände

Mon, 16 Jan 2017 17:31:21 +0000

Das kann man nicht allgemein beantworten.
Man kann bei Kellerautomaten zum Beispiel verschiedene Zustände benutzen, wenn man in einem Zustand Zeichen in den Keller schreiben und in dem anderen Zustand Zeichen aus dem Keller löschen möchte.
Beispiel: $a^nb^n$ . Man könnte zum Beispiel im Zustand $s_0$ die a's in den Keller schreiben, bis man zum ersten b gelangt. Dann könnte man in den Zustand $s_1$ wechseln, um die a's wieder aus dem Keller zu löschen.

Ansonsten kommt es aber immer auf die Aufgabe an, ob und wann es Sinn macht, einen neune Zustand zu definieren.

Viele Grüße
Julia (Tutorin)

Beantwortet: Alternativlösung Kellerautomat

Fri, 13 Jan 2017 10:31:58 +0000

Leider funktioniert das so nicht. Dein Automat erkennt folgende Wörter: $(ab)^m(ba)^n$. Es müsste also noch überprüft werden, ob wirklich m=n gilt, damit der Automat wirklich die Sprache L akzeptiert.

Viele Grüße,
Julia (Tutorin)

Beantwortet: der Automat würde doch auch abbaa akzeptieren oder?

Sat, 16 Jan 2016 12:49:47 +0000

Hallo,

damit ein Kellerautomat ein Wort akzeptiert, muss er sich in einem Endzustand befinden UND das Wort vollständig abgearbeitet sein (siehe Folie 3-5) Der Automat kann zwar für abbaa in den Zustand s2 wechseln, da aber das Wort nicht komplett abgearbeitet ist, wird es nicht akzeptiert.

Viele Grüße

Gregor (Tutor)

Beantwortet: lösung

Mon, 11 Jan 2016 14:34:32 +0000

Noch ein weiterer Hinweis zu Alternativlösungen: Sie können auch denXWizard nutzen, um Ihre Lösungen zu überprüfen.

Das Skript zu Ihrer Lösung wäre:

pda:

(s0,a,k)=>(s0,ak);

(s0,b,a)=>(s0,ba);

(s0,a,b)=>(s0,ab);

(s0,b,b)=>(s1,lambda);

(s1,a,a)=>(s1,lambda);

(s1,lambda,k)=>(se, k);

--declarations--

s0=s0;

F=se;

kSymb=k;

inputs=ababbaba

--declarations-end--

Hier ist die Berechnung für $ababbaba$:

@[ID-24647]@

Dort sehen Sie auch, dass genau der Fall, der von Marvin angesprochen wurde, nicht abgedeckt ist.

Beantwortet: Anfangszustand/Determinismus

Thu, 07 Jan 2016 15:32:47 +0000

Hey uudji,

du hast richtig erkannt, dass das leere Wort akzeptiert werden muss. Da s0 ein Endzustand ist und der Automat kein Wort abzuarbeiten hat, wird das leere Wort auch wirklich akzeptiert.
Eine Überführung muss nicht definiert werden, der Automat in der Musterlösung ist deterministisch (siehe Definition des KA auf Folie 4 Kapitel 3 der Vorlesung).

Zu deiner allgemeinen Frage: Das kommt natürlich ganz auf die Sprache an, ob ein Zustandswechsel nach dem ersten Zeichen notwendig ist. Falls dieser nicht notwendig sein sollte, spielt es keine Rolle ob in s0 mehrere Iterationen durchgeführt werden oder nach dem ersten Zeichen der Zustand gewechselt wird. Der Automat würde die gleiche Sprache akzeptieren und es wäre eine, wie du sagtest, "formale Überführung".
In dieser Aufgabe ist dies jedoch NICHT so. Angenommen deine genannte Überführung (s0, a, ko) → (s0,a) würde zur Zustandsüberführungsfunktion des Automaten gehören, dann wüde der Automat das Wort a akzeptieren, da s0 ein Endzustand ist. Dabei ist a kein Wort der Sprache.
Du merkst, der Grund liegt hier in der Akzeptanz des leeren Wortes: Der Automat springt nach dem Einlesen des ersten Zeichens in den Zustand s1, da dieser kein Endzustand ist um das Wort (das nun gewiss aus mindestens einem Zeichen besteht) auf die Erfüllung der Bedingungen zu überprüfen.

Viele Grüße
Ashvin

Beantwortet: keller-automat

Mon, 04 Jan 2016 13:48:50 +0000

Hallo ugemt,

der Lösungsvorschlag ist falsch (fehlerhafte/nicht erreichbare Übergänge, nicht mal das Testwort ist erkennbar und erst recht nicht die gesamte Sprache) und nicht vollständig, sowie nicht eindeutig als Kellerautomat erkennbar.

Das primäre Problem scheint allerdings die Allgemeinheit des Kellerautomaten zu sein, denn ein Kellerautomat soll die gesamte Sprache erkennen, nicht nur das Testwort (dieses wird also zur Erstellung des Kellerautomaten nicht sonderlich beachtet). Ein Kellerautomat wird i.d.R. wie folgt definiert:

KA = (E, S, K, $\delta$, $s_0$ ,$k_0$ , F) mit:

E ist Eingabealphabet, also alle Zeichen die der KA ´liest´

S ist die Menge der Zustände

K ist das Kelleralphabet, also alle Zeichen die in den Kellergeschrieben werden können (und gelesen)

$\delta$ ist die Überführungsfunktion, welche den Folgezustand und den Kellereintrag in Abhängigkeit vom Zustand, gelesenen Zeichen und oberstem Kellerzeichen angibt (Bsp: $(s_0, a, k_0) -> (s_1, ak_0)$ bedeutet, dass im Zustand $s_0$, bei Lesen vom Zeichen a und oberstem Kellerzeichen in den Keller ak0 geschrieben wird (a kommt also „obendrauf“) und in den Zustand s1 überführt wird.

$s_0$ ist der Anfangszustand

$k_0$ ist das unterste Kellerzeichen (Indikator, dass der Keller leer ist)

und F die Menge der Endzustände.

Als kleiner Tipp zur Erstellung von einfachen Kellerautomaten (o.B.d.A.):

Ein einfacher KA soll oftmals eine Sprache erkennen, welche eine Art „Wendepunkt” aufweist (hier: $(ab)^i (ba)^i$, wobei der „Wendepunkt“ zwischen den beiden Klammern liegt). I.d.R. kommen nach dem Wendepunkt k-mal soviele Zeichen wie vor dem Wendepunkt (hier genauso viele nur in umgekehrter Reihenfolge).

Dieser Kellerautomat kann also einfach gesagt den vorderen Teil eines Wortes nacheinander in den Keller schreiben und danach (ab dem Wendepunkt) für jede richtigen k Zeichen (hier 1) wiederrum ein Zeichen aus dem Keller löschen (Beachte: die Reihenfolge und erlaubte Zeichen müssen beachtet werden). Vereinfacht erkennt der KA also die Sprache, sobald der Keller wieder leer ist und das Wort komplett gelesen wurde.

Die kleine Hilfe ist natürlich nicht auf alle Kellerautomaten übertragbar, sondern soll lediglich die ersten Male die Erstellung eines einfachen Kellerautomaten unterstützen. Natürlich gibt es in den Vorlesungsunterlagen/ -aufzeichnungen genauere und umfangreichere Erläuterungen zu Kellerautomaten.

Weiterhin viel Erfolg,

Marvin (Tutor)

Beantwortet: vorgehensweise

Sun, 03 Jan 2016 22:04:03 +0000

Hallo ugemt!

Nein, es gibt keinen Algorithmus oder feste Vorschriften, wie man einen Kellerautomat konstruiert (außer natürlich, dass seine formale Definition der in der Vorlesung vorgestellten Form und Regeln entsprechen muss).

Das Verstehen der Funktionsweise von Kellerautomaten ist zwar nur der erste, aber dafür ein sehr wichtiger Schritt, den du ja schon gemeistert hast! Am Anfang ist es sicherlich hilfreich, sich ein paar Aufgaben durchzulesen und anschließend gründlich mit der Musterlösung auseinanderzusetzen. Dadurch bekommt man einen Eindruck davon, inwiefern man den Keller nutzen kann, um dort Informationen zwischenzuspeichern (denn das ist ja genau der Vorteil und Grund, warum wir uns mit Kellerautomaten statt mit Endlichen Automaten beschäftigen), beispielsweise das "Abzählen" gleicher Mengen an 1 und 0 in einem Wort, indem man z.B. alle 1 im Keller speichert und dann wieder rauslöscht, sobald eine 0 im Wort vorkommt.

Solche Beispiele bzw. Grundüberlegungen kann man meist auch auf andere Aufgaben übertragen, wobei natürlich meist eine gewisse Transferleistung nötig ist, was vielen Studenten am Anfang Probleme bereitet. Die Devise lautet hier ganz klar: "Übung macht den Meister". Je mehr Kellerautomaten-Aufgaben du gemacht hast, desto mehr Ideen wirst du bekommen, wie man eine Aufgabe prinzipiell lösen könnte.

Und es gibt nie die eine richtige Musterlösung! Meist können ganz verschiedene Herangehensweisen zum richtigen Ergebnis führen, d.h. zwei Kellerautomaten können ganz unterschiedlich arbeiten und trotzdem genau die gleiche Sprache erkennen!

Ich kann dir also leider keine eindeutige Antwort auf deine Frage geben, wie man Kellerautomaten generell konstruiert. Ich hoffe, dass dich meine Antwort aber trotzdem motiviert, dich weiter mit Kellerautomaten auseinanderzusetzen, und ich bin sicher, dass du mit ein wenig Übung und Ausprobieren schnell selbst Vorschritte erkennen wirst!

Viele Grüße,
Janine (Tutorin)

Beantwortet: Lösungsvorschlag

Sun, 03 Jan 2016 19:24:53 +0000

Hey ugemt,

nein deine Lösung für die Zustandsüberführungsfunktion ist nicht richtig.

Der Automat akzeptiert zwar das Testwort abba, aber nicht allgemein die Wörter
(ab) hoch i (ba) hoch i.
Für i=2 (ababbaba) gäbe es für das zweite a beispielsweise keinen Zustandsübergang bzw. allgemein für diese "Schleife" der ersten i ab's nicht.

Hinweis: Wenn ich mir deinen Automaten komplett betrachte, akzeptiert er sogar nur das Wort abba (bzw. das leere Wort für F={s0,se}), da einige Funktionen gar nicht ausgeführt werden können, da die Konstellation aus Zustand, Eingabesymbol und Kellersymbol für diese Funktionen nicht erreicht werden kann.

Falls du zu dieser Aufgabe weiterhin Fragen haben solltest bzw. genauere Antworten benötigtst, dann frag an dieser Stelle gerne weiter!

Viele Grüße
Ashvin (Tutor)

Beantwortet: Deterministische und nichtdeterministische Kellerautomaten

Fri, 16 Jan 2015 14:53:55 +0000

Hallo,

das Problem hierbei ist, dass nach einem deterministischen Kellerautomaten und nicht wie bei KEL-AB nach einem (...) Kellerautomaten gefragt ist.

Würdest du hier (s$_0$, Lambda, k$_o$) schreiben, wäre dein Kellerautomat nichtdeterministisch, da man Lambda, theoretisch zwischen jeden Buchstaben des Eingabealphabets schreiben könnte, und somit nie weiß ob man jetzt gleich in den Endzustand wechseln kann, und somit fertig wäre.

Im Endeffekt wird das Problem das wir haben aber durch eine Kleinigkeit die bei A={....} steht gelöst. Nämlich die Endzustände sin in diesem Fall sowohl s$_0$ als uch s$_e$ (A={.....{s$_0$, s$_e$}), heißt wenn du das leere Wort darstellen willst, dann bleibst du einfach in s$_0$, machst nichts und bist fertig.

Ich hoffe das hilft. ;)

Viele Grüße,

Marc (Tutor)

Beantwortet: Oberster Kellerinhalt richtig angeben

Thu, 15 Jan 2015 13:13:02 +0000

Hallo Peter,

Das genügt leider nicht, und zwar aus folgendem Grund:

es gibt 2 Aktionen die passieren können, wenn man davon ausgeht dass schon ein a (wie bei deinem Beispiel) drin liegt:

1. Das b, das du hier in den Kellerautomaten eingibst wird in den Keller "gelegt", daraus folgt (s$_1$, ba). ba sind hier die letzten beiden "obersten" in den Keller gelegten zeichen.

Ggf hier wäre noch kein a sondern der Keller ist leer dann schreibst du (s$_1$,bk$_0$) um zu zeigen dass du das b hinzufügst und unter dem b nichts mehr steht.

2. Wenn du das b in den Keller gibst, löscht dieses da a (beispielsweise wenn du schauen möchtest ob das Wort das du einliest genau so viele b's wie a's hat. Dann kommst du zu dem Zustand (s$_1$, Lambda), da das a und das jetzt gelsene b "veschwinden".

Wenn du bei 2. den keller komplett leer hast schreibst du k$_0$, um zu symbolisieren dass im Keller nichts mehr steht.

Außer Lambda und k$_0$ schreibt man rechts immer 2 Zeichen (aa, ab, ba, bb, ak$_0$,...), nämlich die letzten die beim "drauflegen" oben liegen.

Ich hoffe das hilft ;)

Viele Grüße,

Marc (Tutor)

Beantwortet: Dann fehlt hier $(s_0, \lambda, k_0) \rightarrow (s_e, k_0)$?

Fri, 09 Jan 2015 15:49:50 +0000

Hallo!

Nein, dieser Zustandsübergang ist nicht nötig, da der Startzustand s_0 selbst ein Endzustand ist, dh. wenn du nichts eingibst ( entspricht der Eingabe des leeren Wortes lambda), dann ist der Kellerautomat im Startzustand s_0, der aber gleichzeitig auch ein Endzustand ist.

Außerdem wäre der Kellerautomat dann nicht-deterministisch, wenn du diesen Zustandsübergang auch noch definieren würdest, was nach der Aufgabenstellung ("Geben Sie einen deterministischen Kellerautomaten A an") sogar falsch wäre!

Hier also aufpassen: So viele Zustandsübergänge definieren wie nötig, aber so wenig wie möglich (wegen der Gefahr, dann einen nichtdeterministischen Kellerautomaten zu erzeugen) !

Gruß, Janine (Tutorin)

Beantwortet: Endzustand

Fri, 09 Jan 2015 08:02:24 +0000

Hallo,

$s_0$ ist auch ein Endzustand, da in dieser Sprache auch das leere Wort erlaubt ist.

Viele Grüße,

Sebastian (Tutor)

Beantwortet: Fehlt in Musterlösung der Übergang zum Sackgassenzustand (s0,b,k0)?

Wed, 12 Nov 2014 08:13:52 +0000

http://info2.aifb.kit.edu/qa/index.php?qa=1151&qa_1=warum-sind-%C3%BCberg%C3%A4nge-sackgassenzustand-nicht-aufgef%C3%BChrt

Siehe Post von Lukas (Tutor) zum Thema Sackgassenzustände bei det. Kellerautomaten.

Gruß,

Tobias (Tutor)

Beantwortet: Warum folgt nach Eingabe von a und b wieder a?

Wed, 12 Nov 2014 08:10:30 +0000

Also die Sprache beinhaltet z.B. folgende Wörter:

- das leere Wort

- abba

- ababbaba

also genausoviele "ab" Teilwörter hintereinander wie im Anschluss "ba" Teilwörter vorkommen.

Wir wollen also nicht (!) nur "abba" beliebig oft hintereinanderschreiben.

Gehen Sie bitte die Lösung nochmal mit diesem Ansatz durch, ich bin mir sicher, dass dann einiges klarer wird, sollten dennoch Fragen offen sein können Sie gerne noch einmal nachfragen.

Mit freundlichen Grüßen

Alexander (Tutor)

Beantwortet: Warum sind Übergänge zum Sackgassenzustand nicht aufgeführt?

Wed, 12 Nov 2014 08:08:36 +0000

Hallo,

ein Kellerautomat benötigt, anders als ein Endlicher Automat, keine Sackgackgassenzustände! Der Kellerautomat akzeptiert ein Wort nur dann, wenn das Wort komplett abgearbeitet wurde und er sich anschließend in einem Endzustand befindet. Wenn das Wort noch nicht abgearbeitet ist, und es keinen passenden Übergang mehr gibt, lehnt er das Wort automatisch ab.

Das leere Wort ist in der Musterlösung enthalten, weil s0 als Endzustand definiert wurde.

Viele Grüße

Lukas (Tutor)

Beantwortet: Weiterer alternativer Lösungsvorschlag Kellerautomat

Wed, 12 Nov 2014 08:05:09 +0000

Hallo,

also von der Idee her ist es gut. Jedoch gibt es bei Kellerautomaten leider keinen Übergang, indem man das oberste Kellerzeichen zu einem anderen umschreibt.

Gruß,

Adam (Tutor)

Beantwortet: Alternativer Lösung Kellerautomat

Wed, 12 Nov 2014 08:04:10 +0000

Dein Kellerautomat erkennt auch das Wort "ababba". Dieses Wort ist aber erlaubt. Du merkst dir mit deiner Vorgehenseise nicht wie viele "ab" du zu Beginn eingelesen hast.

Beantwortet: Warum muss "ba" nicht akzeptiert werden?

Wed, 12 Nov 2014 08:03:07 +0000

Das Wort ba ist nicht Teil der Sprache, da zwar i=0 möglich ist, dann handelt es sich aber um das leere Wort, da (ab) und (ba) immer gleichhäufig vorkommen müssen (i-mal)

Viele Grüße

Christiane (Tutorin)

Beantwortet: Warum Konfiguration (s1, a, a) nicht notwendig?

Wed, 12 Nov 2014 08:00:01 +0000

Die Wörter müssen laut der formalen Beschreibung der Sprache folgendermaßen aufgebaut sein:

w = (ab)^i(ba)^i

Beispielwörter wären also: abba, ababbaba

d.h. mit "bb" wird der "Umkehrpunkt" im Wort markiert.

In der Lösung werden zunächst alle abab...eingelesen (Zustände s0 und s1)

Der Umkehrpunkt "bb" führt dann zum Zustandsübergang (s1,b,b)-->(s2,lamda), d.h. ab hier werden mit Zustandsübergängen aus s2 heraus die Zeichen wieder aus dem Keller gelöscht.

Es kann hier keine Konfiguration (s1,a,a) geben, weil "aa" nicht als Umkehrpunkt zulässig ist. Ein Einlesen von "a" und ein oberstes Kellerzeichen "a" können erst auftreten, wenn der Umkehrpunkt "bb" schon durchlaufen wurde, also erst ab s2.

Ich hoffe das war verständlich soweit.

Viele Grüße,

Melanie (Tutorin)

Beantwortet: Wann Kellerautomat deterministisch/nichtdeterministisch?

Wed, 12 Nov 2014 07:56:57 +0000

Hallo,

das Zitat, welches Sie hier nennen, bezieht sich auf das Hinzufügen des folgenden Übergangs: (s0, lambda, k0) -->... .
Da der Automat aber auch den Übergang (s0, a, k0) --> ... enthält, wäre der KA somit nichtdeterministisch.

Bei folgenden Aussage "Ich verstehe nicht, was hier der Unterschied zu dem Teil der Musterlösung ist, in dem in Zustand s1 für das Zeichen b sowohl bei a als auch bei b ein Übergang definiert ist." verstehe ich leider nicht, worauf Sie sich beziehen.

Freundliche Grüße
Friederike Pfeiffer

Beantwortet: Warum hier R0?

Wed, 12 Nov 2014 07:54:26 +0000

Warum denn nicht? Somit ist einfach auch das leere Wort in der Sprache enthalten.

Viele Grüße
Friederike Pfeiffer

Beantwortet: Vorgehensweise Konstruktion eines Kellerautomaten, der das leere Wort akzeptiert

Wed, 12 Nov 2014 07:52:45 +0000

Das sind zwei Möglichkeiten. Achten Sie aber auf den Determinismus / Nichtdeterminismus.

Viele Grüße
Friederike Pfeiffer

Beantwortet: Hilfe bei Erstellung deterministischer Kellerautomat

Wed, 12 Nov 2014 07:51:35 +0000

Sie müssen bei der Lösung hier beachten, dass nicht nur se sondern auch s0 ein Endzusand ist. So gewährleisten Sie, dass das leere Wort auch erkannt wird und der Automat deterministisch bleibt.
Beachten Sie aber hierbei auch, dass Sie bei der ersten Eingabe den Zustand von s0 nach s1 wechseln müssen, um zu gewährleisten, dass Sie keine "falschen" Worte erkennen.

Viele Grüße
Friederike Pfeiffer