Warum Konfiguration (s1, a, a) nicht notwendig?

Question

Warum muss es hier keine Konfiguration (s1, a, a) geben? Kann das Wort nicht mit zwei a's anfangen?

Answer 1

Die Wörter müssen laut der formalen Beschreibung der Sprache folgendermaßen aufgebaut sein:

w = (ab)^i(ba)^i

Beispielwörter wären also: abba, ababbaba

d.h. mit "bb" wird der "Umkehrpunkt" im Wort markiert.

In der Lösung werden zunächst alle abab...eingelesen (Zustände s0 und s1) 

Der Umkehrpunkt "bb" führt dann zum Zustandsübergang (s1,b,b)-->(s2,lamda), d.h. ab hier werden mit Zustandsübergängen aus s2 heraus die Zeichen wieder aus dem Keller gelöscht.

Es kann hier keine Konfiguration (s1,a,a) geben, weil "aa" nicht als Umkehrpunkt zulässig ist. Ein Einlesen von "a" und ein oberstes Kellerzeichen "a" können erst auftreten, wenn der Umkehrpunkt "bb" schon durchlaufen wurde, also erst ab s2.

Ich hoffe das war verständlich soweit.

Viele Grüße,

Melanie (Tutorin)

 

Comments

Achso natürlich stimmt. Ich habe die Beschreibung erst falsch verstanden.

Ja,vielen Dank!