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

Beantwortet: zustandsübergang bei KA

Mon, 10 Feb 2020 16:18:41 +0000

Doch müsste auch gehen.

LG, Nico (Tutor) (Alle Angaben ohne Gewähr)

Beantwortet: Ndet. Kellerautomaten Verständnis

Mon, 10 Feb 2020 10:43:38 +0000

Hallo,

Hast du ein Beispiel im Sinn, das deine Frage weiter erläutert?

LG,

Beantwortet: Verständnisfrage (nicht-)deterministische Automaten

Sat, 11 Jan 2020 14:56:18 +0000

Hallo unveh,

ja, natürlich kannst Du einen deterministischen Kellerautomat in diesem Fall angeben. Dennoch ist es normalerweise einfacher, einen nicht deterministischen Kellerautomat zu erzeugen.

Viele Grüße,

Runxi (Tutorin)

Beantwortet: Kellerautomat - Mehr als ein Zeichen auf den Stack legen

Thu, 18 Jul 2019 13:33:37 +0000

https://info2.aifb.kit.edu/qa/index.php?qa=3539&qa_1=darf-ich-in-den-keller-was-anderes-schreiben-als-ich-lese&show=3539#q3539

Zitat Lukas König: "Vielleicht noch zur Ergänzung: Man darf nicht nur jedes Zeichen auf den Keller schreiben, das im Kelleralphabet steht, sondern auch beliebige Kombinationen von Zeichen aus dem Kelleralphabet. Man darf also sowohl

λ auf den Keller schreiben, als auch ein einzelnes Kellerzeichen als auch belibig lange Ketten von Kellerzeichen. Gelesen wird dabei aber immer nur ein einziges Zeichen, das oberste, und dieses wird vor dem Schreiben aus dem Keller gelöscht.

Schauen Sie sich als Bespiel für Kellerautomaten, die mehr als ein Zeichen auf den Keller schreiben, ruhig mal das Verfahren an, um aus einer kontextfreien Grammatik einen Kellerautomaten zu machen.

Auch der XWizard kann das, klicken Sie bei dieser Grammatik mal auf die Konversions-Methode "Kellerautomat":

http://www.xwizard.de:8080/Wizz?template=ID-12630#Output

Es kommt ein Automat heraus, der an einer Stelle aSb auf den Keller schreibt, also ein Zeichen löscht und drei neue schreibt."

Beantwortet: Anmerkung Nichtdeterminismus

Tue, 09 Feb 2016 23:07:55 +0000

Hallo uudtm!

Ja, durch das Weglassen der ersten Übergangsregel und stattdessen der Definition von s_0 als Endzustand würde sich an der Funktionsweise des Kellerautomaten tatsächlich nichts ändern, das wäre also zulässig.

Nichtsdestotrotz bleibt dein Kellerautomat insgesamt nicht-deterministisch (was ja auch im Aufgabentext explizit so gefordert wird) wegen dem in der Anmerkung erwähnten doppelten Übergang von (s_1,a,a) und den Übergängen (s_2,lambda, k_0) gekoppelt mit (s_2, c, k_0).

Ich hoffe, das beantwortet deine Frage!

Viele Grüße,
Janine (Tutorin)

Beantwortet: Alternativer Lösungsvorschlag

Fri, 05 Feb 2016 12:04:09 +0000

Hallo,

so ist das nicht ganz möglich, da du so keine Kontrolle darüber hast ob eine gerade Anzahl von c's vorliegt.

Also bietet es sich an das c in den Keller zu schreiben und mit dem 2. C wieder herauszulöschen.

Viele Grüße,

Marc (Tutor)

Beantwortet: Weshalb braucht man den Zustand s1?

Sat, 09 Jan 2016 11:42:38 +0000

Hallo,

der Zustand s1 ist hier nur zur Übersichtlichkeit eingefügt, man könnte hier durchaus auch für "lese ein a ein", im Zustand s0 bleiben, und somit alle Überführungen von s1 im Zustand s0 durchführen.

Zu deiner zweiten Frage:
Du kannst einen 2. Zustand definieren und mit diesen immer wieder hin und herswitchen, ohne etwas in den Keller zu schreiben, allerings finde ich macht es das komplizierter und unübersichtlicher, als einfach einmal das c hinein zu schreiben und bei dem nächsten wieder herauszulöschen, aber das ist Geschmackssache. ;)

Ich hoffe ich konnte dir weiterhelfen, falls noch Fragen bestehen, einfach hier drunter posten :)

Viele Grüße,

Marc (Tutor)

Beantwortet: Benennung der Zustände

Fri, 16 Jan 2015 18:19:21 +0000

Hallo,

wie du die Zustände nennst ist prinzipiell erst einmal egal. Du kannst den nächsten zustand s$_1$, s$_2$, s$_9$ nennen, das ist dir überlassen.

Der Grundgedanke der hier dahinter steht ist der.

Nachdem du in s$_0$ gestartet bist und wir annehmen dass ein a gefallen ist, wechselst du in s$_1$. hier bleibst du so lange bis ein c oder b fällt. fällt ein c wechselst du in s$_2$, und musst schauen dass nun eine gerade Anzahl von c's eingegeben werden. Nachdem alle c's (eine gerade Anzahl!) abgelegt wurden und sich so selbst aus dem Keller "gelöscht" haben, kommst du bei dem Eintrag von b, so wie in dem Fall wenn gleich nach dem a ein b kommt, zum Zustand s$_3$, indem pro b ein a gelöscht wird. Fällt kein b sondern gleich ein a, bzw fällt nun nach dem b ein a gelangst du in den Zustand s$_4$ indem sich durch die eingegebenen a's, die a's die im Keller stehen rauslöschen.

Ist der Keller leer und gibt es keinen weiteren Zustand den du eingeben kannst, kommst du in den Endzustand und die Aufgabe ist beendet.

Viele Grüße,

Marc (Tutor)

Beantwortet: Alternativer Lösungsvorschlag

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

Deine Idee mit Hilfe der Zustände auf eine gerade Anzahl von c's zu kommen ist grundsätzlich möglich.

Mir sind beim Anschauen aber drei Sachen aufgefallen:

1. Was passiert, wenn das Wort nur aus c's besteht (Bsp: cccc)? Das Wort ist Teil der Sprache wird aber nicht erkannt.

2. Bei deiner Lösung könnten Wörter erkannt werden, die nach einem b noch einmal c's haben (Bsp: aaccbcca)

3. Was passiert wenn das Wort nur aus a's besteht (Bsp:aa)? Hier brauchst du z.B. einen nichtdeterministischen Übergang (s1,a,a)-->(s3,lambda)

Gruß Jörg (Tutor)

Beantwortet: Uneindeutigkeit Kellerautomat

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

Hallo,

du hast schon Recht: Jedes Wort, was erzeugt werden kann, ist automatisch Teil der Sprache. Das heißt auch bei ndet KA muss man schauen, dass man nicht zu viele Wörter erkennen kann. Bei der uneindeutigkeit kann es nur zu Sackgassenzuständen kommen, das ist aber kein Problem, solange ich immer einen Weg für jedes Wort meiner Sprache finde.

Bei deiner Überführungsfunktion stimmen leider einige Übergänge nicht bzw. fehlen. Drei Beispiele:

1) Das einzige Wort, das nur aus c's besteht, ist bei dir das Wort cc. Jedoch sollen alle Wörter c^(2r) darstellbar sein.

2) Wenn ich a's am Anfang schreibe, z.B. aaaa, dann kann ich danach nur mit einem b weiter machen und kann kein c schreiben.

3) Der Übergang (s2, c, k0) -> (s2, λ) macht keinen Sinn, du kannst k0 nicht aus dem Keller löschen.

Schau dir das am Besten nochmal an.

Gruß,

Adam (Tutor)

Beantwortet: Notwendigkeit Zustandswechsel/Zustände

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

Richtig, der Automat wird u.a. deswegen uneindeutig, also nicht deterministisch. Ein Wort wird bei einem n det KA erkannt, wenn es eine Konfigurationsfolge gibt, die in einem Endzustand endet. Dabei spielt es dann also keine Rolle, dass man auch eine Konfigurationsfolge wählen könnte, die nicht in einen Endzustand kommt.

Ja beide Zustände sind nötig. Wenn man nur einen benutzt, würde man a´s aus dem Keller löschen, wenn die Eingabe b oder a kommt. Somit könnten sich im hinteren Teil des Wortes (also nach den c´s) b´s und a´s auch abwechseln, was aber nicht sein darf (Bsp. für ein Wort, das dann fälschlicherweise erkannt werden würde: aaaccbab)

Sven (Tutor)

Beantwortet: Erstellung der Konfigurationsübergänge Kellerautomat

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

Grundidee für diesen Kellerautomaten:
Es soll ein Kellerautomat zu einer Sprache gebildet werden, die folgende Wörter enthalten: w = a^m c^q b^n a^p, mit der Einschränkung, dass die Anzahl a's (vorne) gleich der Anzahl von b's und a's (hinten) sind. Zudem werden diese durch die c's getrennt, deren Anzahl aber gerade ist. Demnach:

1. Es werden alle a's in den Keller gelesen (um diese später mit den b's und a's zu vergleichen)
2. Anschließend werden die c's eingelesen, dabei wird immer ein c in den Keller geschrieben, und mit dem nächsten c wird dieses wieder aus dem Keller gelöscht. So können Sie überprüfen, dass die Anzahl der c's gerade bleibt.
3. Wenn nun das erste b auftritt, dann fangen Sie an, die a's, die am Anfang in den Keller geschrieben wurden, wieder zu löschen. Das gleiche wird für die anschließenden a's gemacht. Am Ende darf nichts mehr im Keller liegen, sonst stimmen die vorgegebenen Anzahlbedingungen nicht.

Das ist die Grundidee: Nun müssen Sie noch geeignete Zustandswechsel einführen, um zu gewährleisten, dass die Reihenfolge von a, c, b, a erhalten bleibt und hier nichts durcheinander gerät.
Zudem müssen Sie noch überprüfen, welche "Ausnahme"Übergänge Sie brauchen, wenn z.B. gar keine c's auftauchen oder keine b's, ... (siehe Einträge oben).

Ich hoffe, dass Ihnen das weiter hilft.

Freundliche Grüße
Friederike Pfeiffer