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

Übungsaufgabe 43

0 Punkte
91 Aufrufe
Hallo,

ich vestehe die Sprache so: Es werden alle Wörter akzeptiert die in ihrer zweiten Hälfte (nach $\$$) immer das Komplement ihrer ersten Hälfte enthalten, also zum Beispiel: $aa\$bb$, $b\$a$, $ab\$ba$,... ist das so korrekt?

Wenn ja, verstehe ich die vorvorletzte und vorletzte Zeile bei der Konfiguration des KA nicht. Es müsste dann statt

$(s_1,a,a) \rightarrow (s_1,\lambda)$

$(s_1,b,b) \rightarrow (s_1,\lambda)$

eher

$(s_1,a,b)\rightarrow(s_1,\lambda)$

$(s_1,b,a)\rightarrow(s_1, \lambda)$

sein.

Kann mir jemand weiterhelfen?
Gefragt 17, Jan 2018 in Band I, Kapitel 5 von Anonym  
Bearbeitet 17, Jan 2018 von Lukas König
Wie kann es eigentlich sein, dass so viele von Ihnen nicht wissen, wie man lamBda schreibt?

Eine Antwort

0 Punkte
Als Beispiel wird das Wort "aab$baa" akzeptiert. 
und wenn wir im Zustand s1 sind, sind wir mit der Bearbeitung der 2.Hälfte (nach $)beschäftigt. 
bzw. vorher wurde aab(1.Hälfte) im Keller gespeichert, und im Zusatand s1 wird zuerst "b" (in der 2.Hälfte) mit "b" (in der 1.Hälfte) gelöscht d.h (s1, b, b) --> (s1, lamBda)
 
dann erstes "a" (nach b in der 2.Hälfte) wird mit letztes "a" (vor b in der 1.Hälfte) gelöscht (s1, a, a) --> (s1, lamBda) usw.
 
d.h. immer die 2 Zeichen, die gelöscht werden möchten, müssen gleich sein.
 
u´ ist der Palindrom von u. zB: u=aab     u´=baa
Palindrom:  eine Zeichenkette, die vorwärts wie rückwärts gelesen identisch ist.
 
Kann ein Übungsleiter/Tutor meine Antwort bestätigen/korrigieren?
 
(Antwort ohne Gewähr, bin kein Tutor)
Beantwortet 17, Jan 2018 von uldvb uldvb Lernwillige(r) (980 Punkte)  
Bearbeitet 19, Jan 2018 von uldvb uldvb
Genau, bei der Sprache handelt es sich um Palindrome, die in der Mitte ein $ enthalten. Damit ist deine Antwort genau richtig.
Viele Grüße,
Julia (Tutor)
...