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

Beliebteste Tags

verständnis alternativlösung klausur kellerautomat endlicher-automat grammatik regulärer-ausdruck pumpinglemma turingmaschine tipp zahlendarstellung cmos klausurrelevant bonusklausur komplexität schaltwerk binary-decision-diagram deterministisch assembler schaltnetz minimierung sprachen nichtdeterministisch huffman chomsky-normalform fehler-in-aufgabe anwesenheitsübung rechtslinear heimübung flip-flop cocke-younger-kasami-algorithmus kontextsensitive-grammatik kontextfreie-grammatik fehlererkennbarkeit huffman-kodierung hauptklausur vorlesungsfolien kontextfreie-sprache polynomialzeitreduktion faq gleitkommazahl fehlerkorrigierbarkeit rechtslineare-grammatik dateiorganisation cache darstellung-klausur nachklausur xwizard adressierungsarten lambda mealy konjunktive-normalform pipelining zustände saalübung leeres-wort endliche-automaten ohne-lösungen betriebssystem speicherorganisation moore monotone-grammatik 2-komplement fehler reguläre-sprache hammingzahl monoton lösungsweg pumping-lemma-für-kontextfreie-sprachen kodierung berechenbarkeit pumping-lemma klausureinsicht disjunktive-normalform info-ii bussysteme rechnerarchitektur abzählbarkeit komplexitätsklassen ableitungsbaum vorlesungsaufzeichnung round-robin minimierung-endlicher-automaten chomsky-klassen von-neumann-rechner binärzahl entscheidbar programmiersprachen entscheidbarkeit aufzählbarkeit stern-symbol automaten schaltnetze-und-schaltwerke nukit-fragen bewertung zugriffsarten umformung adressierung mengen binär-subtrahieren

Kategorien

0 Pluspunkte 0 Minuspunkte
120 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?
in Band I, Kapitel 5 von  
Bearbeitet von
0 0
Wie kann es eigentlich sein, dass so viele von Ihnen nicht wissen, wie man lamBda schreibt?

1 Eine Antwort

0 Pluspunkte 0 Minuspunkte
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)
von uldvb uldvb Lernwillige(r) (980 Punkte)  
Bearbeitet von uldvb uldvb
0 0
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)
...