Theoretische und technische Informatik - ganz praktisch - Letzte Aktivität in 2011-B-02

Antwort ausgewählt: Zustandwechsel am Anfang notwendig

Mon, 13 Jan 2020 20:51:35 +0000

Hallo urgwq,

was du dadurch erzeugen würdest wäre ein nichtdeterministischer Kellerautomat, durch den nichtdeterministischen Übergang, den du eingefügt hast.

Da aber in der Aufgabenstellung nach einem deterministischen Kellerautomat gefragt wurde, brauchst du s0 als Endzustand und den Übergang zu s1.

Ich hoffe das konnte deine Frage klären.

Viele Grüße

Alex (Tutor)

Kommentiert: Ist das Wechseln von s1 in s2 notwendig?

Thu, 12 Jan 2017 21:26:13 +0000

Hallo,

ja da hast du recht, das Beispiel war unpassend gewählt. Dafür sollte das Wort aacacc den Wiederspruch zeigen den ich gemeint habe (wenn mich nicht alles täuscht :D).
(s0, aacacc, k0) -->(s1, acacc, ak0)--> (s1, cacc, aak0)--> (s1, acc, ak0)--> (s1, cc, aak0)-->(s1, c, ak0)--> (s1, lambda, ak0)--> (se, k0)

Grüße, Sören (Tutor)

Beantwortet: ist s3 notwendig?

Mon, 09 Jan 2017 15:59:25 +0000

Hier kann man s3 nicht weglassen, sonst könnte ich, wenn ich dann in s0 bin, quasi wieder anfangen und neue Zeichen einlesen.

Das Wort abccabcc würde damit z.B. erkannt werden, was jedoch nicht Teil der hier definierten Sprache ist.

Grüße, Sören (Tutor)

Beantwortet: Darf ich in den Keller was anderes schreiben, als ich lese?

Sun, 17 Jan 2016 12:48:57 +0000

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 $\lambda$ 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: Können prinzipiell mehrere KA richtig sein?

Tue, 29 Sep 2015 10:09:57 +0000

Es ist oft der Fall, dass es mehrere mögliche richtige KA gibt. Meistens ist in der Musterlösung die einfachste/effizienteste Antwort dargestellt.

Wenn die in der Aufgabe gestellten Anforderungen erfüllt sind, dürfte es keinen Abzug geben.

Gruß Jörg (Tutor)

Beantwortet: Akzeptiert KA auch Wörter die zu viele c's enthalten?

Tue, 29 Sep 2015 10:08:24 +0000

Du hast Recht, wenn alle a's und b's abgearbeitet sind, macht der Automat einen lambda Übergang. Erhält das Wort aber mehr c's also a's+b's, dann landen wir in einem Endzustand, aber das Wort ist nicht vollständig abgearbeitet, das Band ist also nicht leer, und das ist eine Voraussetzung dafür, dass ein Wort von einem KA akzeptiert wird:

Endzustand + Wort vollständig abgearbeitet

Gruß,

Adam (Tutor)

Kommentiert: Könnte man nicht bei den ersten beiden Übergängen in s0 bleiben?

Tue, 29 Sep 2015 10:07:08 +0000

Hallo,

Ein KA ist nicht deterministisch, wenn es zwei Übergänge gibt, die der Automat zur selben Zeit ausführen könnte. Einfaches Beispiel:

(s0,a,k0)->(s0,ak0)

(s0,a,k0)->(s0,bk0)

Lese ich also am anfang ein a, dann erfülle ich die Voraussetzung für beide Übergänge und weiss nicht, welche ich ausführen soll (d.h. die Definition der Erkennung bei ndet. KA: Wenn es eine Folge von Überführungen gibt, sodass es akzeptiert wird, dann ist es Teil der Sprache).

Schauen wir uns jetzt speziell das mit dem lambda übergang an. Wir hätten also

(s0,lambda,k0)->(se,k0)

(s0,a,k0)->(s0,ak0).

Dies ist beides ausführbar, wenn mein Wort mit einem a beginnt! Denn das lambda dort heißt nicht, dass dieser Übergang verwendet werden darf, wenn kein Buchstabe gelesen wird, also das Band leer ist. Ein lambda Übergang darf immer gemacht werden, wenn Zustand und Kellerzeichen übereinstimmen.

Würde also ein a gelesen werden, dürfte ich trotzdem einen lambda-Übergang machen! Und genau so geht der Determinismus verloren und deshalb muss auch der Anfagnszustand ein Endzustand sein, wenn das leere Wort Teil der Sprache ist. Denn die einzige Alternative ist der lambda Übergang, den haben wir aber gerade augeschlossen.
Gruß, Adam (Tutor)

Beantwortet: Vereinfachung möglich?

Tue, 29 Sep 2015 10:05:30 +0000

Das hätten Sie hier auch machen können, das würde einige Übergänge sparen.

Viele Grüße

Friederike Pfeiffer-Bohnen und Lukas König

Beantwortet: Wann genau ist ein KA nicht deterministisch?

Tue, 29 Sep 2015 10:04:15 +0000

Hallo,

zu der ersten Frage:

Das hat nichts mit dem Determinismus zu tun. der Wechseln in s2 kommt, damit nur Wörter akzeptiert werden, die am Anfang a's und b's haben und am Ende alle c's. Würdest du den Zustand nicht wechseln, könntest du z.B. das Wort abccab erkennen, obwohl das Wort nicht Teil der Sprache ist.

Zur zweiten Frage:

Würdest du nach s0 wechseln, könntest du auch wieder mehr Wörter akzeptieren. Z.B. abccabcc. Nach abcc würdest du dann mit einem lambda-Übergang nach s0 wechseln und alles nochmal machen. Das Wort darf aber nicht akzeptiert werden.

Gruß,

Adam (Tutor)