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.)

Erklärung der Übergänge

–1 Punkt
33 Aufrufe
Könnte mir jmd die Übergänge erklären? Die sind mir irgendwie nicht so eindeutig...
Gefragt 22, Okt 2014 in KEL-AF von utdbu utdbu Tutor(in) (106,580 Punkte)  

Eine Antwort

0 Punkte

Hallo,

hier ist eine grobe Beschreibung der Idee:

Zuerst einmal wissen wir, dass die Wörter aus der Sprache eine gerade Anzahl an b's haben und immer auf aab enden müssen.

s0 = Startzustand, und Zustand, in dem die Anzahl der b's gerade ist 

s1 = Zustand, in dem die Anzahl der b's ungerade ist

s2 = Zustand, der nach dem ersten a schaut, ob das zweite a folgt

s3 = Zustand, der nach dem zweiten a schaut, ob ein b folgt

se = Endzustand

Wenn wir in s0 starten und ein b einlesen, dann haben wir eine ungerade Anzahl an b's, also rüber in s1. Beim nächsten b in s1 sind wir wieder im geraden Bereich, also wechseln wir zurück in s0. Und so kann man dann hin und her wechseln solange wir weiter b's einlesen.

Wenn wir in s0 sind und ein a einlesen, dann wissen wir, dass wir uns damit schon im Endteil "aab" des Wortes befinden müssen. Also wird der Zustand gewechselt in s2, und dort an wird dann weiter geprüft, ob der weitere Verlauf des Wortes wirklich "aab" entspricht.

Hoffe, das konnte dir einen Überblick verschaffen :)

Viele Grüße,

Vivian (Tutor)

 

Beantwortet 22, Okt 2014 von utdbu utdbu Tutor(in) (106,580 Punkte)  
Dass einzige was mich noch leicht verwirrt, ist, das am Ende immer ko steht.
Hallo,

lass dich nicht davon verwirren. Hier steht am Ende immer ko, weil unserer Kellerautomat den Keller gar nicht benutzt bzw. braucht. Allerdings gibt es mehrere richtige Lösungen und es ist egal ob du den Keller benutzt oder nicht.

Einfachere Sprachen können ohne den Keller erkannt werden, aber für komplexere Sprache ist sowas nicht mehr möglich. Z.B für die Sprache a^nb^n brauchst du den Keller  um die Sprache erkennen zu können, weil du irgendwie zählen muss, wie viele a bzw b vorgekommen sind.

Grüße

Antonio

(Tutor)
...