Theoretische und technische Informatik - ganz praktisch - Letzte Fragen & Antworten in 2011-B-02

Beantwortet: Zustandwechsel am Anfang notwendig

Sun, 12 Jan 2020 15:15:31 +0000

Hallo urgwq

Wenn du dir bei deiner Lösung deine ersten drei Übergänge anschaust, da hast du ja zum Beispiel die Möglichkeiten:

1) Erstes Zeichen ist ein 'a': Ich lese im Startzustand (s0) und leerem Keller (oberstes Kellerzeichen k0) ein 'a' ein und bleibe in s0 oder ich lese '

Beantwortet: Ist das Wechseln von s1 in s2 notwendig?

Thu, 12 Jan 2017 20:17:44 +0000

Hallo,

ja der Zustandswechsel ist hier notwendig. In deinem Fall würden sonst beispielsweise auch Wörter wie abccabcc erkannt werden. Da ich ja ein c einlese und weiterhin in S1 bin kann ich im Anschluss also beispielsweise wieder ein a einlesen. Das ist bei den Wörtern der Sprache jedoch nicht der Fall. Sobald einmal ein c eingelesen wurde dürfen nur noch c kommen und zwar genau n+m viele.

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)

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)

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

Tue, 29 Sep 2015 10:02:56 +0000

Hallo,

in diesem Fall muss man in den Zustand s1 wechseln, da das leere Wort Teil der Sprache ist und anderenfalls dein Automat nicht deterministisch wäre! (Denn dann dürfte s0 kein Endzustand sein und du bäruchtest einen lambda Übergang der Form (s0,lambda,k0), womit dein Automat nicht mehr deterministisch ist!)

Gruß,

Adam (Tutor)