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

Beantwortet: Automat in Aufgabe 41 a) nichtdeterministisch?

Fri, 28 Jan 2022 21:16:24 +0000

Hallo,

da sowohl bei Aufgabe 41, als auch bei Aufgabe 44 ein Lambda-Übergang notwendig ist, um den Automaten vollständig zu definieren, sind beide Automaten damit auch direkt nichtdeterministisch.

Bei einem Lambda-Übergang findet ein Zustandsänderung statt, ohne dass etwas in den Keller geschrieben, bzw. eingelesen wird. Dieser ist immer automatisch ein nichtdeterministischer Schritt, da man theoretisch alternativ auch das nächste Zeichen des abzuarbeitenden Wort "bearbeiten" könnte (Siehe Tut 2).

Beantwortet: verstandnis problem

Sun, 02 Jan 2022 11:15:48 +0000

Hallo uqyxt,

Die Wörter der Sprache besteht aus den Wiederholungen der Zeichenfolge aab (also z.B. aabaabaab).

Die Idee der ersten Zeile ist, dass das 1. a dieser Folge eingelesen und in den Keller gepusht wird.
In der dritten Zeile wird das 3. a dieser Folge eingelesen und das a im Keller bleibt einfach stehen. Hier muss auch der Zustand gewechselt werden, weil wir sonst nicht mehr aus der dritten Zeile nicht mehr herauskommen (kannst du ja mal ausprobieren, was passiert wenn statt s₁ s₀stehen würde)
In der vierten Zeile wird nun das b eingelesen und das a im Keller gepopt. Damit haben wir einmal die Zeichenfolge aab eingelesen und wechseln in den Endzustand.
Im Endzustand geht es aber weiter mit dem Einlesen des nächsten a und das Ganze fängt von vorne an (fünfte Zeile).
Nun soll aber auch das leere Wort akzeptiert werden, weshalb wir einen einen λ-Übergang von s₀ brauchen (zweite Zeile). Dies macht den Kellerautomaten dann nichtdeterministisch.

Ich hoffe, das hilft dir weiter.

Grüße
Jahn (Tutor)

Beantwortet: Neue Zeichenkette Keller-Automat

Mon, 15 Jan 2018 11:51:29 +0000

Hallo,

ist deine Frage warum hier:

(s0, a, a) -> (s1, a)

auf der rechten Seite (s1, a) und nicht (s1, a k0) steht?

Da links (s0, a, a) steht wird mit dem zweiten a definiert, dass dieser Übergang nur ausgeführt wird, wenn ein a oben ist. Also könnte rechts gar nicht (s1, a k0) stehen, sondern höchstens (s1, a a), dies würde aber (anders als mit (s1, a)) ein weiteres a in den Keller schreiben.

Wenn du noch schreibst um welche Aufgabe es geht, kann ich gerne auch konkret darauf eingehen.

Viele Grüße

Niklas (Tutor)

Beantwortet: Alternativlösung (a)

Tue, 25 Jul 2017 16:51:51 +0000

Hi,

deine Lösung ist auch Korrekt.

Hier muss den Keller eigentlich gar nicht benutzt werden. Du hättest z.B. auch einfach immer k_0 wieder in der keller schreiben können und nur den Kellerzustand wechseln.

Viele Grüße,

Kaleb

Beantwortet: Übungsaufgabe 41a)

Fri, 10 Feb 2017 12:15:21 +0000

Hallo,

ein Kellerautomat akzeptiert ein Wort genau dann, wenn er sich in einem Endzustand befindet und das Wort komplett abgearbeitet hat.

Was dann genau im Keller steht ist für das Akzeptanzverhalten des Automaten irrelevant.

Zur Aufgabe 41a):

Der Keller ist bei Eingabe des Testwortes "aab" leer (bis auf das Kellersymbol k0). Schau dir dazu nochmal Zeile 3 der Zustandsüberführungsfunktion an. Das zweite a wird nicht auf das bereits im Keller stehende a geschrieben, sondern es ersetzt das a im Keller, sodass danach immernoch nur ein a im Keller steht. (sonst wäre die Schreibweise: s1,aa). Das b löscht dann dieses eine a aus dem Keller, und es bleibt nur noch k0 übrig.

Liebe Grüße,

Christian (Tutor)

Beantwortet: Alternative Lösung?

Mon, 06 Feb 2017 23:12:38 +0000

Mir sind persönlich ist ein kleiner Fehler aufgefallen:

(s0, a, k0) →(s1,ak0)

wenn da nur ein a steht, heißt das, dass du das a stehen lässt. Also nichts dem Keller hinzufügst oder löschst. Da zu Beginn dort ein k0 steht ist diese Zustandsüberführung nicht zulässig.

Anonsten dürfte es stimmen.

Beantwortet: Wieso Sprache von Typ 1?

Sun, 14 Feb 2016 11:05:32 +0000

Hallo,

ich glaube du bringst da etwas durcheinander.

Bei Grammatiken müssen wir ggf. aufpassen, da z.B. eine Typ 2 Grammatik nicht auch automatisch vom Typ 1 ist (hier machen uns eventuell die λ-Übergänge Probleme). Dennoch können wir durch umformen zu jeder Typ 2 Grammatik auch eine vom Typ 1 finden.

Bei unseren Sprachklassen dagegen gilt, dass jede Sprache vom Typ i auch vom Typ i-1 ist (für i=1,2,3).

Hat das deine Frage beantwortet?

Viele Grüße,

Tim (Tutor)

Beantwortet: Kellerautomaten für n=2,3...

Sun, 07 Feb 2016 11:34:29 +0000

Hallo uqdrx!

Dein Fehler liegt darin, dass ja nicht alle 4 a's nacheinander kommen, sondern das Wort bei n=2 ja heißt : aabaab

Nun wird mit (s0,a,k0) -> (s0, ak0) das erste a in den Keller geschrieben. Mit (s0,a,a) -> (s1,a) wird, wie du selbst richtig erkannt hast, kein weiteres a in den Keller geschrieben, sondern das im Keller stehende a mit dem a, das auf dem Band gelesen wurde, überschrieben (also weiterhin nur ein a im Keller) und der Kellerautomat geht in Zustand s1 über.

So, und nun folgen eben zunächst keine weiteren a's (es gibt auch gar keinen Übergang (s1,a,a,) -> ... , denn laut Sprachdefinition dürfen nicht mehr als 2 a direkt hintereinander stehen), sondern es folgt der Übergang (s1,b,a) -> (se,lambda), durch den das eine a im Keller gelöscht wird und der Automat in den Endzustand se übergeht. Das Wort könnte hier beendet werden (n=1) oder der Prozess beginnt von vorne mit (se,a,k0) -> (s0,a), wie es im Falle n=2 geschieht.

Ich hoffe, das hilft dir weiter!

Viele Grüße,

Janine (Tutorin)

Beantwortet: Verständnis

Sat, 06 Feb 2016 14:53:33 +0000

Hallo uqdrx!

Dadurch, dass L von dem in Aufgabenteil b) definierten Endichen Automaten erkannt werden kann, handelt es sich um eine Sprache vom Typ 3 (vgl. Folie GdInfoII 2-72).

Nach Satz aus der Vorlesung (vgl. Folie GdInfoII 1-17) gilt außerdem, dass jede Sprache vom Typ i auch vom Typ i-1 ist (für i=1,2,3).

Ich hoffe, das hilft dir weiter!

Viele Grüße,
Janine (Tutorin)

Beantwortet: Verständnisproblem

Sat, 09 Jan 2016 19:02:06 +0000

Hey ubelq,

genau! Zur Sprache gehören nicht die Wörter $a^{2n}$ $b^n$ sondern $ {(a^{2} b)}^n$.
Also für n=2 nicht aaaabb sondern aabaab.

Viele Grüße
Ashvin (Tutor)

Beantwortet: Lösung

Sat, 09 Jan 2016 00:29:12 +0000

Hallo ugemt,

dieser Kellerautomat ist zwar nicht minimal (wird hier allerdings nicht gefordert), aber er kann die Sprache erkennen.

Bitte beim nächsten Mal den KA komplett angeben:

$ A = \{ \{ a , b \} , \{ s_0 , s_1 ,s_2 , s_e \} , \{ k_0 , a, b \} , s_0 , k_0 , \{ s_e \} \} $

$ (s_0 , a, k_0) \rightarrow (s_0 , ak_0) $

$ (s_0, a, a) \rightarrow (s_1,a) $

$ (s_1,b,a) \rightarrow (s_1,b) $

$ (s_1, a , b) \rightarrow (s_0,a) $

$ (s_1, \lambda,b) \rightarrow (s_2, \lambda) $

$ (s_2, \lambda, k_0) \rightarrow (s_e, k_0) $

Weiter so,

Marvin (Tutor)

Beantwortet: Lösungsvorschlag

Fri, 08 Jan 2016 21:37:33 +0000

Hallo ugemt,

diese Veränderung funktioniert leider nicht, da z.b. das Testwort $aab$ nicht erkannt wird und nicht zugelassene Wörter wie $aabaaaba$ erkannt werden.

Viel Erfolg,
Marvin (Tutor)

Beantwortet: Alternativlösung

Fri, 08 Jan 2016 16:12:20 +0000

Hallo ugemt,

der angegebene Kellerautomat:

$$A = \{ \{ a, b \} , \{ s_0, s_1,s_2, se \}, \{ k_0, a, b \} , \delta , s_0, k_0 , \{ s_e \} \} $$

$$ \delta : \{ (s_0, a, k_0) ->(s_0 . ak_o ) $$

$$ (s_0, a,a ) ->(s_0 , a) $$

$$ (s_0, b ,a) ->(s1, \lambda) $$

$$(s_1, \lambda, k_0) ->(s_e, k_0) $$

$$ (s_1, a, k_0 ) ->(s_0, ak_0) \} $$

ist nicht richtig, da dieser nicht unterscheiden kann, ob ein $a$ oder mehrere $a$ kommen ( $(s_0, a,a ) ->(s_0 , a) $ ). Somit akzeptiert er auch Woerter, die nicht Teil der Sprache sind.

Weiterhin viel Erfolg,

Marvin (Tutor)

Beantwortet: Verständnisproblem

Mon, 13 Jul 2015 12:14:13 +0000

Hallo,

ja, für diese Aufgabe hätte auch ein deterministischer Kellerautomat ausgereicht. Wie später gezeigt wird, gibt es ja sogar einen endlichen Automaten für die Sprache, also ist da sogar ein DKA noch "unterfordert".

Nichtdeterministisch ist der Automat aus der Lösung nur, weil es einfacher ist, so einen anzugeben und weil in der Aufgabenstellung kein DKA gefordert war.

Viele Grüße

Lukas König

Beantwortet: Alternativlösung: mit b zwei a's löschen

Thu, 15 Jan 2015 16:03:01 +0000

Hallo,

so geht das leider nicht, denn du kannst immer nur auf das oberste Kellerzeichen zugreifen. Dann hast du 4 Möglichkeiten: du entfernst es, du behältst es einfach bei, du ersetzt es oder du fügst ein neues hinzu. Etwas anderes geht nicht.

Beantwortet: Heißt das, nur der Übergang $(s_0, \lambda, k_0) \rightarrow (s_e, k_0)$ macht den KA ndet?

Fri, 09 Jan 2015 09:17:54 +0000

Sie haben das richtig verstanden. Durch die beiden Übergänge $(s_0, \lambda, k_0) \rightarrow (s_e, k_0)$ und $(s_0, a, k_0) \rightarrow (s_0, ak_0)$ wird der Automat nichtdeterministisch. Würde nur einer der beiden Übergänge existieren, dann wäre der Automat deterministisch, aber da man, wenn als nächstes ein a gelesen wird (und k_0 im Keller ist), sich zwischen dem Einlesen von a und $\lambda$ entscheiden kann, ist der Automat nichtdeterministisch. Nichtdeterministisch bedeutet, dass man an irgendeiner Stelle des Automat die Wahl zwischen zwei Übergängen hat. Beachten Sie hierbei aber, dass dabei das oberste Kellerzeichen gleich ist. Folgender Übergang würde den Automaten auch nichtdeterministisch machen: $(s_1, b, a) \rightarrow (s_1, ba)$, da Sie noch den Übergang $(s_1, b, a) \rightarrow (s_e, \lambda)$ haben.

Beantwortet: Möglicher alternativer Kellerautomat

Wed, 07 Jan 2015 14:14:43 +0000

Wie Sebastian schon geschrieben hat, ist dieser Kellerautomat auch korrekt. Damit Sie ein besseres Gefühl dafür bekommen, wie der Rechenweg eines ndet. Kellerautomaten aussieht, habe ich mal einen für das Wort aabaab und Ihren Autmaten aufgestellt. Daran sehen Sie auch, dass der ndet. Übergang

$$(s_0, \lambda, k_0) \rightarrow (s_e, k_0)$$

bzw.

$$(s_0, a, k_0) \rightarrow (s_0, ak_0)$$

nur dazu da ist, das leere Wort zu erkennen. Daher ergibt sich nur zu Beginn eine Verzweigung und danach zwei parallele Rechenwege, die am Ende beide akzeptieren (doppelt gerahmtes Rechteck). Da das immer so ist, können Sie den Automaten auch deterministisch machen, indem Sie den Übergang

$$(s_0, a, k_0) \rightarrow (s_0, ak_0)$$

weglassen (wenn ich gerade nichts übersehe). Dadurch arbeitet der Automat einen Rechenschritt länger, weil er am Anfang IMMER den $\lambda$-Übergang nehmen muss, ist dafür aber deterministisch.

Beantwortet: Deterministische Alternativlösung

Thu, 06 Nov 2014 11:18:38 +0000

korrekt: denke ja

deterministisch: ja.

Tobias (Tutor)

Beantwortet: Wie sieht es mit dieser Alternativlösung aus?

Thu, 06 Nov 2014 10:58:26 +0000

Hallo,

das sieht auch richtig aus!

Grüße,

Jördis (Tutorin)

Beantwortet: Verständnisproblem

Thu, 06 Nov 2014 10:55:15 +0000

Hallo,

nein, man schreibt zuvor nur ein $a$ in den Keller.

Das zweite $a$ bewirkt den Übergang $(s_0, a, a) \rightarrow (s_1, a)$.

Beim Kellerautomat muss man das so verstehen, dass das oberste Zeichen ersetzt wird durch das, was im rechten Tupel rechts steht. Nur wenn es $(s_1, aa)$ heißen würde, würde man ein zweites $a$ reinschreiben (man würde dann das alte $a$ durch ein neues ersetzen und zusätzlich noch eins darüber schreiben).

Der Zustand $s_1$ ist es, was dir hier anzeigt, dass zwei $a$'s dem $b$ voraus gingen, nicht die Zahl der $a$'s im Keller.

Somit wird durch den $b$-Übergang nur das eine $a$ gelöscht und man ist wieder ganz unten im Keller.

Viele Grüße

Philippe (Tutor)

Beantwortet: Alternativlösung auch korrekt?

Thu, 06 Nov 2014 10:51:11 +0000

Hallo,

sieht gut aus.

Gruß,

Adam (Tutor)

Beantwortet: Frage zur Terminierung des KA

Thu, 06 Nov 2014 10:46:46 +0000

Es reicht dann $s_0 \in F$ als Bedingung (wenn $s_0$ kein Endzustand sein soll, kann aber einen Übergang $(s_0, \lambda, k_0) \rightarrow (s_e, k_0)$ sinnvoll sein). Beachten Sie, dass bei $\lambda$-Übergängen der Automat nicht deterministisch werden KANN (aber nicht muss).

Viele Grüße

Lukas König

Beantwortet: Wann akzeptiert der KA?

Thu, 06 Nov 2014 10:42:56 +0000

Nein, das Wort würde er nicht akzeptieren, da nach dem Einlesen der ersten 3 Zeichen für die Situation $(s_e,b,k_0)$ kein Übergang definiert ist. Der KA ist dann zwar in einem Endzustand, aber nicht alle Zeichen auf dem Eingabeband wurden eingelesen, was auch Voraussetzung für das Akzeptieren eines Wortes ist (s. Folie 3-7 d) )

Sven (Tutor)

Beantwortet: Anderer Lösungsvorschlag

Thu, 06 Nov 2014 10:34:02 +0000

Das ginge so ohne den ersten Übergang. Was bezwecken Sie mit dem Übergang

$$(s_0, \lambda, k_0) \rightarrow (s_0, k_0)$$

Das macht nicht wirklich Sinn, da Sie beim Einlesen von $\lambda$ nicht den Zustand wechseln, was normalerweise der Sinn eines Lambda-Übergangs ist. So können Sie theoretisch eine unendliche Ableitungsfolge generieren.

Freundliche Grüße

Friederike Pfeiffer

Beantwortet: Verständnisproblem

Thu, 06 Nov 2014 10:29:58 +0000

Deine Umformung ist falsch. Du wendest hier Regeln der Mathematik (Arithmetik) an. $a$ und $b$ sind aber keine numerischen Variablen, die für Zahlen stehen sondern Zeichen aus einem Alphabet. Wörter, die erkannt werden sollen, sind: $\lambda, aab, aabaab, aabaabaab, \ldots$

Viele Grüße,

Sven (Tutor)

Beantwortet: Ich habe eine andere Lösung

Thu, 06 Nov 2014 10:26:26 +0000

Ich gehe nun mal davon aus, dass bei Ihnen $s_1$ Endzustand ist? Dann wäre der obere Teil bei Ihnen korrekt, als folgender:

$$(s_0, a, k_0) \rightarrow (s0, ak_0) \\ (s_0, \lambda, k_0) \rightarrow (s1, k_0) \\ (s_0, a, a) \rightarrow (s_0, b) \\ (s_0, b, b) \rightarrow (s_0, \lambda)$$

Beachten Sie aber, das Ihr Automat nicht-deterministisch ist. Was jedoch macht bei Ihnen der Übergang

$$(s_0, a, b) \rightarrow (s_0, ab)$$

Das verstehet ich nicht.

Viele Grüße

Friederike Pfeiffer

Beantwortet: Einfachere Lösung möglich?

Thu, 06 Nov 2014 09:57:54 +0000

Wenn ich das richtig sehe, dann würde das so nicht gehen, da Sie dann beliebig viele $a$'s hintereinander einlesen können. Sie müssen ja gewährleisten, dass immer zwei $a$'s gelesen werden und dann ein $b$ kommt. Erst dann dürfen Sie wieder $aab$ einlesen.

Viele Grüße

Friederike Pfeiffer

Beantwortet: Lösung unnötig kompliziert?

Thu, 06 Nov 2014 09:37:55 +0000

"Es müsste doch einfach folgendes gehen:

$(s_0, \lambda, k_0) \rightarrow (s_e, k_0)$

$(s_0, a, k_0) \rightarrow (s_1, k_0)$

$(s_1, a, k_0) \rightarrow (s_1, A)$

$(s_a, b, A) \rightarrow (s_0, \lambda)$"

Sie müssten hier folgendes ändern:

$$(s_a, b, A) \rightarrow (s_0, \lambda)$$

$$(s_1, b, A) \rightarrow (s_0, \lambda)$$

Dann würde es so funktionieren. Der einzige wirkliche Unterschied zwischen Ihrer Lösung und der Musterlösung ist, dass Sie, wenn $aab$ gelesen wurde, in $s_0$ gehen und von dort entweder weiter machen, falls das Wort noch nicht fertig abgearbeitet wurde, oder von dort in $s_e$.

In der Musterlösung gehen wir zuerst in $s_e$ und, falls das Wort noch nicht fertig abgearbeitet wurde, wieder in $s_0$. Das macht den einen Zustandsübergang mehr aus.

Aber vorsicht, auch Ihre Lösung ist nicht-deterministisch wegen:

$$(s_0, \lambda, k_0) \rightarrow (s_e, k_0),\\ (s_0, a, k_0) \rightarrow (s_1, k_0)$$

Wenn Sie $s_0$ zum Endzustand machen, dann wären Sie wieder deterministisch.

Viele Grüße

Friederike Pfeiffer

Beantwortet: Ich verstehe den letzten Übergang der Lösung nicht

Thu, 06 Nov 2014 09:15:30 +0000

Im Keller befinden sich nie 2 $a$.

$$(s_0,a,a) \rightarrow (s_1,a)$$

überschreibt das im Keller vorhandene $a$ durch ein $a$. Der Keller bleibt also unverändert. Mit

$$(s_0,a,a) \rightarrow (s_1,aa)$$

könnte man 2 $a$ in den Keller schreiben. Ich vermute das war dein Probem.

Sven (Tutor)

Beantwortet: Wäre auch diese Lösung möglich?

Thu, 06 Nov 2014 09:12:02 +0000

Der zweite Übergang kann so nicht erfolgen, da das oberste Kellerzeichen in $s_1$ immer ungleich $k_0$ ist. Mit $(s_1,a,a) \rightarrow (s1,b)$ müsste es klappen.

Viele Grüße,

Sven (Tutor)