Verständnisproblem

Question

Leider verstehe ich auch nach Ihren Begründungen noch nicht, wieso keine 1 am Anfang stehen darf.

Zwar erscheinen mir ihre Erläuterungen zu den Regeln als verständlich, allerdings implizieren diese für mich nicht, dass eine 0 am Anfang stehen muss.

Comments

wie ist der Code aus Aufgabenteil c) zu verstehen?

Answer 1

Hallo,

wie sie sicher schon bemerkt haben, wird die Sprache implizit über Codewörter definiert von denen man schon weiß, dass sie Teil der Sprache sind. Gehen wir nun davon aus sie kennen bisher nur das in der Aufgabenstellung angegebene Codewort 0101 0101. Jetzt müssen sie zur Ableitung anderer Codewörter eine Partition sabt=0101 0101 wählen und dann gemäß der angegebenen Regeln das neue Codewort ableiten.

Schaut man sich die Regeln an, so bemerkt man, dass s und t immer erhalten bleiben (für die Frage ist vorallem s relevant). Lediglich die Teile a und b werden entweder vertauscht oder ersetzt.

Um jetzt ein Codewort mit einer 1 am Anfang zu generieren, bleibt als einzige Chance die Wahl s=lambda (also das leere Wort), denn ansonsten würde s erhalten bleiben und somit wieder eine 0 am Anfang des Codewortes stehen.

Ist s aber das leere Wort, so muss t länger sein als s und somit greift die mittlere der angegebenen Regeln, bei denen vor den Teil t zwei 0en geschrieben werden. Das neue Codewort hat also am Anfang zwei Nullen und nicht eine 1 wie wir es uns vorher erhofft hatten.

Wir haben jetzt zwar angenommen, dass wir bisher nur das eine angegebene Codewort der Sprache kannten, aber eigentlich haben wir bewiesen, dass wenn wir bisher nur Codewörter kennen die mit einer 0 beginnen, es nicht möglich ist ein Codewort abzuleiten, dass mit einer 1 anfängt. Induktiv folgt dann, dass ein Wort mit einer 1 am Anfang überhaupt nicht in der Sprache vorkommen kann.

Ich hoffe das hilft weiter.

Christian (Tutor)

Comments

Hallo,

aus der Aufgabenstellung geht doch nur hervor, dass 01010101 ein Element des Codes ist und die darunter stehenden Regeln für die Bildung weitere Codewörter gelten sollen. Mir ist nicht klar, wieso das gegebene Codewort die Bildung weiterer Codewörter einschränken soll, da nach den Regeln s,t aus {0,1}* und a,b aus {0,1} gewählt werden kann.

Danke

---

Sie müssen jetzt mal einen Schritt zurücktreten und sich auf eine andere Art zu denken einstellen als Sie offenbar gewohnt sind. Da steht doch, dass Codewörter nur aus $sabt$ erzeugt werden dürfen, wenn $sabt$ selbst schon ein Codewort ist. Versuchen Sie das mal zu verstehen! Das ist eine etwas andere Art als wir sonst Codes definieren, aber aus Grammatiken kennen Sie so eine Vorgehensweise auch schon.

---

Vielen Dank für die Antwort!

Also heißt das, dass ich aus bekannten Codewörtern = sabt gemäß den "Ableitungsregeln" neue Codewörter erzeuge, indem ich das bekannte Codewort 01010101 in s,a,b,t zerlege und daraus neue Wörter bilde?

Also z.B s= 01 ,t =0101 und dann folgt aus |s|<|t|: 01000101

PS.: Die Bemerkung bzgl. der Vorgehensweise bei Grammatiken hat sehr geholfen!

---

Genau. Und wenn Sie dann ein neues Wort abgeleitet haben, dann können Sie auch dieses als Grundlage nehmen. Es beginnt mit dem einen vorgegebenen Wort, wie beim Zeichen $S$ bei Grammatiken, aber danach können Sie sich alle bisher abgeleiteten Wörter auswählen, um $sabt$ darauf zu verteilen (ebenfalls wie bei Grammatiken).