Übungsaufgabe 43

Question

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?

Comments

Wie kann es eigentlich sein, dass so viele von Ihnen nicht wissen, wie man lamBda schreibt?

Answer 1

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)

Comments

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)