Theoretische und technische Informatik - ganz praktisch
Herzlich willkommen auf der Question/Answer-Plattform zu Grundlagen der Informatik II. Wir wünschen Ihnen viel Spaß beim Lernen und Diskutieren!
Loggen Sie sich mit Ihrem KIT-Account (u...) ein, um loszulegen!
Beachten Sie auch diese Informationen zum Schnelleinstieg.
(Nicht-KIT-Studierende beachten bitte diese Informationen.)

Schöne Ferien!
 

 

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

–1 Punkt
95 Aufrufe
Warum muss es hier keine Konfiguration (s1, a, a) geben? Kann das Wort nicht mit zwei a's anfangen?
Gefragt 12, Nov 2014 in KEL-AE von uyctv uyctv Info-Genie (19,150 Punkte)  

Eine Antwort

0 Punkte

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)

 

Beantwortet 12, Nov 2014 von uyctv uyctv Info-Genie (19,150 Punkte)  
Achso natürlich stimmt. Ich habe die Beschreibung erst falsch verstanden.

Ja,vielen Dank!
...