Theoretische und technische Informatik - ganz praktisch - Letzte Fragen & Antworten in 2014-N-07

Beantwortet: Aufgabe 7

Sun, 21 Mar 2021 18:01:48 +0000

Hallo,

0101 0101 (=:w) ist ein spezielles Wort aus C, mit diesem kannst du andere Wörter aus C bilden.

Beispiel: w ist aus C, dann ist auch 01001101 aus C (hier ist s=010,a=1,b=0,t=101 und damit auch sbat aus C). und 01000101 ist aus C (s=01,t=0101, damit ist auch s00t aus C). So kann man weiter Vorgehen und die anderen Wörter bestimmen. Mit allen neu generierten kann man dann wieder alle Fälle separat durchgehen.

In der rechten Spalte der Tabelle wird jeweils der Fall |s|=|t| von der linken Seite betrachtet, die Lücken haben also keinen tieferen Sinn.

Die Wörter die du angibst gehören (glaube ich) nicht zu C, in a) stehen alle möglichen Wörter, die zu C gehören.

Falls du noch Fragen dazu hast, kannst du einfach fragen.
Viele Grüße

Codewörter angeben?!

Sun, 11 Feb 2018 09:30:55 +0000

Hallo zusammen,

mir ist im aufgabenteil a) nicht ganz klar, wieso einige wörter in der Antwort nicht enthalten sind,

Generell ist mir die Lösung mit der angegeben Tablle nicht klar.

Konkret verstehe ich zum Beispiel nicht, warum 0110 nicht korrekt ist.

Und wieso hat die Tabelle 4 Zeilen? Verstehe ich es ebenfalls richtig, dass die erste Spalte für den Code, der durch sabt erstelt wird steht und die zweite Spalte für den Code, der einen der drei Bedingnungen erfüllen muss?

Beantwortet: Verständnisproblem

Wed, 08 Feb 2017 12:30:24 +0000

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)

Beantwortet: b): Warum gilt nicht Hc = 1 ?

Wed, 23 Sep 2015 12:31:36 +0000

Steht nicht genau das in der Lösung:

Lösung:

1, denn 0101 0101 und 0100 0101 sind Codewörter.

Max (Tutor)

Beantwortet: Warum kann man keine Wörter bilden, die mit einer 1 beginnen?

Wed, 23 Sep 2015 12:28:41 +0000

Hallo,

Sie dürfen s, t, a und b ja nicht einfach beliebig wählen, sondern Sie müssen die vorhandenen Codewörter anschauen und daraus mögliche Belegungen dieser Variablen ableiten. Beispielsweise haben wir zu Beginn nur das Codewort

\( 0101 0101 \)

in der Sprache. Eine mögliche Belegung wäre jetzt bspw.

\( s=010, a=1, b=0, t=101 \)

Daraus ergibt sich nach der ersten Regel in der Fallunterscheidung (da \( |s| = |t| \) ), dass

\( sbat = 01001101 \)

ebenfalls in der Sprache ist. Jetzt können Sie auch von diesem neuen Wort ausgehen (aber natürlich auch weiterhin vom ersten) und bspw. festlegen:

\( s=0, a=1, b=0, t=01101 \)

wodurch nach der zweiten Regel in der Fallunterscheidung (da \( |s| < |t| \) )) auch das Wort

\( s00t=00001101 \)

in der Sprache ist. So macht man dann weiter, bis alle Wörter abgeleitet sind.

Viele Grüße

Lukas König

Beantwortet: c): Warum ist "00001111 " nicht enthalten?

Wed, 23 Sep 2015 12:25:45 +0000

Hallo,

wie würden Sie das Wort denn bilden? Die allgemeine Regel ist, dass für alle schon vorhandenen Codewörter an jeder Stelle, wo sich zwei benachbarte Bits "ab" unterscheiden, ein neues Wort dadurch entsteht, dass man alle Bits davor durch "a" ersetzt und alle danach durch "b". Das impliziert aber, dass die im ersten Schritt generierten neuen Codewörter keine weiteren mehr entstehen lassen können, weil diese ja nur eine Stelle haben, wo sich zwei benachbarte Bits unterscheiden, und diese Stelle wurde ja bereits nach der o.a. Regel im ersten Schritt bearbeitet.

Klingt ein bisschen kompliziert, ich hoffe, Sie verstehen, was ich meine.

Viele Grüße

Lukas König

Beantwortet: e): Lösungsvorschlag

Wed, 23 Sep 2015 12:21:59 +0000

Sowohl bei der Fehlererkennbarkeit als auch bei der Fehlerkorrigierbarkeit muss k element der natürlichen Zahlen sein. Daher liegt in diesem Fall die Fehlererkennbarkeit bei 1 und die Fehlerkorrigierbarkeit bei 0.

Lorena (Tutorin)

Beantwortet: a): Vorgehensweise bei Lösung?

Wed, 23 Sep 2015 12:20:37 +0000

Sie müssen sich hier zukzessive durch die Definition arbeiten. Sie wissen am Anfang nur, dass 0101 0101 zum Code C gehört.

Wenn aber 010 10 101 dazugehört, dann gilt folgendes: (Leerzeichen absichtlich so gewählt)

wir wählen Länge von s und t gleich: s=010 und t=010, a=1, b=0 . Wenn aber sabt (mit Länge s = Länge t) zu C gehört, dann gehört auch sbat zu C also 010 01 101 (das zweite Codewort)
wir wählen |s|<|t|: s=01 t=0101 a=0 b=1, dann gehört auch s00t dazu, also 01 00 0101
wir wählen |s|<|t|: s=0 t=10101 a=1 b=0, dann gehört auch s00t dazu, aslo 0 00 10101
wir wählen |s|>|t|: s=0101 t=01 a=0 b=1, dann gehört auch s11t dazu, also 0101 11 01
...

So können Sie auch mit den neu errechneten Codewörtern durchlaufen, bis Sie 6 verschiedene Codewörter zusammen haben.

Ich hoffe, dass das so verständlich war.

Viele Grüße

Friederike Pfeiffer-Bohnen