Theoretische und technische Informatik - ganz praktisch - Letzte Aktivität in KEL-AD

Antwort ausgewählt: zustandsübergang bei KA

Mon, 10 Feb 2020 16:40:45 +0000

Doch müsste auch gehen.

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

Kommentiert: Ndet. Kellerautomaten Verständnis

Mon, 10 Feb 2020 14:58:15 +0000

Hallo,

ich habe die Anmerkung von KEL-AD falsch verstanden, sorry.
Ich dachte es wurden extra Übergänge eingefügt, zusätzlich zu (s0,lamda,k0), um den Automaten nicht-deterministisch zu machen.
Trotzdem danke für die Antwort!

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)

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

Thu, 18 Jul 2019 13:34:00 +0000

https://info2.aifb.kit.edu/qa/index.php?qa=4840&qa_1=s3-1-b-s3-b1-kann-man-kellerzeichen-im-keller-tauschen&show=4840#q4840
Zitat Tutor:"Man kann nur das oberste Kellerzeichen lesen und dann durch ein beliebiges Wort

∈K∗∈K∗ ersetzen.

Bei (s3,1,b)→(s3,b1)(s3,1,b)→(s3,b1) werden nicht die obersten zwei Kellerzeichen getauscht, sondern nur das oberste Kellerzeichen bb durch b1b1 ersetzt. Diese Überführung ist also erlaubt und somit ist auch die Ableitung des Testwortes korrekt.

Viele Grüße

Philipp (Tutor)"

https://info2.aifb.kit.edu/qa/index.php?qa=5992&qa_1=mehrere-kellerzeichen-gleichzeitig-löschen
Zitat Tutor:"Schauen wir uns hierfür ein Teil der Definition aus dem Lehrbuch an (S.49-50):

"Wenn sich der Kellerautomat in Zustand s ∈ S beﬁndet und auf dem Eingabeband e gelesen wird und das oberste Kellerzeichen k ∈ K ist, dann wird k im Keller durch das ganze Wort v ∈ K* ersetzt, indem dieses von hinten nach vorne zeichenweise auf den Keller gepusht wird".

Desweiteren gilt für die Zustandsüberführungsfunktion folgendes:

δ∶ S × (E ∪ {λ}) × K → S × K*

Da der Lese/Schreibe-Kopf des Kellers immer auf dem obersten Kellerzeichensteht und nur dieses liest, sind nur Zustandsübergänge folgender Form erlaubt:

δ(s, e, k) = (s ′ , v) mit s, s' ∈ S, e ∈ E, k ∈ K und v ∈ K*.

k besitzt daher nur ein Element aus K (und nicht wie du es angeben wolltest zwei Elemente (00).

Zusammenfassend können wir also sagen, dass pro Rechenschritt jeweils nur das oberste Zeichen des Kellers überschrieben bzw. gelöscht werden kann."

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)

Kommentiert: Erstellung der Konfigurationsübergänge Kellerautomat

Sat, 06 Feb 2016 16:04:20 +0000

Wie viel Minuten hätte man für so eine Aufgabe Zeit, um sie in der Klausur zu lösen ?

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)

Antwort ausgewählt: Weshalb braucht man den Zustand s1?

Sat, 09 Jan 2016 12:22:36 +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)

Erneut getaggt: Benennung der Zustände

Sat, 17 Jan 2015 06:47:49 +0000

Hallo,

ich verstehe bei dieser Aufgabe nicht so ganz, wieso man z.B. beim dritten Zustandsübergang von (s0,c,k0) in den Zustand s2 wechselt, statt in s1. Denn schließlich würde das c als erster Buchstabe kommen, da kein a davor käme.

Und insgesamt was im s2 genau gemacht wird, ist mir unklar, vor allem der zehnte Übergang mit (s2,c,k0) zu (s2,ck0).

Vielen Dank

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)

Kommentiert: Uneindeutigkeit Kellerautomat

Wed, 22 Oct 2014 16:58:24 +0000

Deine Lösung ist leider falsch. Schau Dir mal das Testwort aaccba an. (s0,aaccba,k0)-->(s0,accba,ak0)-->(s0,ccba,aak0)--> ??

Nun ist kein Zustand mehr definiert. Es gibt kein Zustand mit (s0,c,a)-->...

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)