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 sprachen minimierung nichtdeterministisch huffman fehler-in-aufgabe chomsky-normalform anwesenheitsübung rechtslinear heimübung flip-flop cocke-younger-kasami-algorithmus kontextsensitive-grammatik kontextfreie-grammatik huffman-kodierung hauptklausur fehlererkennbarkeit 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 klausureinsicht disjunktive-normalform pumping-lemma info-ii bussysteme rechnerarchitektur abzählbarkeit komplexitätsklassen ableitungsbaum vorlesungsaufzeichnung round-robin minimierung-endlicher-automaten chomsky-klassen binärzahl entscheidbar programmiersprachen entscheidbarkeit aufzählbarkeit stern-symbol automaten nukit-fragen bewertung zugriffsarten von-neumann-rechner umformung adressierung mengen binär-subtrahieren organsiation

Kategorien

0 Pluspunkte 0 Minuspunkte
242 Aufrufe
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.
in 2014-N-07 von upeco upeco Lernwillige(r) (150 Punkte)  
0 0
wie ist der Code aus Aufgabenteil c) zu verstehen?

1 Eine Antwort

0 Pluspunkte 0 Minuspunkte
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)
von ucefn ucefn Tutor(in) (103k Punkte)  
0 0
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
0 0
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.
1 0
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!
0 0
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).
...