optionales Übungsblatt 2, Aufgabe 8

Question

 Hallo,

ich habe eine Frage zur  Keller Automaten von Aufgabe 8): 

1. ist die Beschreibung von Überführungsfunktion flexibel? oder gibt eine fest Regel (wie in Vorlesung 3 s. 7 steht): ?

Beispiel 1:8a) δ4: (s0; b; a) - (s1; ba): ist hier richtig?  warum schreibt man hier nicht (s0; b; a) - (s1; λ)? da ein b gelesen wurde, dann wird ein a in der Keller gelöscht oder ?

Beispiel 2:8b) δ5: (s0; a; k0) - (s1; ak0): warum muss man hier Zustand wechseln? weil in 8a) ist der Zustand geblieben:(s0; a; k0) -(s0; ak0)

2. kann sein die Lösung  für das Testwort  am Ende ein λ fehlt. 

z.b L4: (s3; λ; k0) -(s4; k0): soll sollte (s4; λ; k0) statt (s4; k0) schreiben oder?

genauso wie bei L5: (s3; λ; k0) ‘ (s4; k0)

3. wie kann man überprüfen, ob Überführungsfunktion komplett geschrieben ist? Gibt ein Verfahren, wie man die Überführungsfunktion schreibt?

Dank sehr im Voraus

Answer 1

Hallo uqyws,

1. Die Beschreibung der Überführungsfunktion ist so geregelt, wie auf den Folien, also etwas in den Keller schreiben und löschen eventuell noch nichts machen. Man braucht also nur die Idee, wie man die Grammatik dann mit diesen Regeln anwenden kann.

Zum Bsp 1: Die Grammatik lautet a^mb^na^nb^m, es gibt also gleich viel a's am Anfang wie b's am Ende und in der Mitte gleich viele b's wie a's. n und m können unabhängig von einander gewählt werden. Im Zustand s0 werden nur die a's gesammelt und gemerkt, bis der Mittelteil (b^na^n) abgearbeitet wurde. Sobald das erste b kommt sind wir im Zustand s1 und merken uns alle b's (und n>=1, also kommt auf jeden Fall ein b). In s2 müssen genau so viele a's kommen wie b's gerade eben (n Stück) und wenn dann alle a's abgearbeitet sind haben wir immer noch m Stück im Keller für die kommenden b's.

Also man braucht die Zustände wirklich aufgrund der Form der Grammatik.

Zu Bsp 2: Man muss nicht zwingend den Zustand wechseln, es geht auch ohne. Zur Strukturierung kann es helfen, in s1 geht man, wenn das Wort nichtleer ist.

2. Du kannst (s4; λ; k0) schreiben, ist auf jeden Fall kein Fehler. Es ist Konvention, dass man das am Ende auch weglassen kann, wenn das Wort abgearbeitet ist und man im Endzustand ist, schaden tut es dennoch nicht.

3. Ein Verfahren gibt es so direkt nicht, man sollte die Grammatik noch einmal anschauen und auch Sonderfälle beachten. Dann kann man seinen Automaten Schritt für Schritt durchgehen, ob die alle berücksichtigt werden. Aber einen garantierten Weg gibt es leider nicht.

Ich hoffe, ich konnte dir weiterhelfen, viel Erfolg noch beim Lernen und viele Grüße

Anne (Tutorin)

Comments

Alles Klar
Vielen Dank