+2 Daumen
1,5k Aufrufe

Aufgabenblatt: Grundbegriffe der Informatik

Sind X und Y zwei Mengen und f : X → Y eine bijektive Abbildung, so ist die Relation

$$R _ { f } = \{ ( f ( x ) , x ) | x \in X \}$$

eine bijektive Abbildung von Y nach X, die wir mit f^{-1} bezeichnen, Umkehrabbildung von f oder Inverse von f nennen, und für die für jedes x ∈ X und jedes y ∈ Y gilt:

$$f ^ { - 1 } ( f ( x ) ) = x \text { und } f \left( f ^ { - 1 } ( y ) \right) = y$$

Es sei A das Alphabet {a, b, c}, es sei γ die bijektive Abbildung

$$\begin{aligned} \gamma : \mathbb { Z } _ { 3 } \rightarrow A \\ 0 \mapsto a \\ 1 \mapsto b \\ 2 \mapsto c \end{aligned}$$

und es sei \( \odot \) die binäre Operation

$$\odot : A ^ { * } \times A ^ { * } \rightarrow A ^ { * }$$

$$( u , v ) \mapsto \left\{ \begin{array} { l l } { u , } & { \text { falls } u = \epsilon \text { oder } v = \epsilon } \\ { \gamma \left( \left( \gamma ^ { - 1 } ( x ) + \gamma ^ { - 1 } ( y ) \right) \bmod 3 \right) \cdot ( \mu \odot \kappa ) , } & { \text { falls } u = x \cdot \mu \text { und } v = y \cdot \kappa } \\ { } & { \text { für } x , y \in A \text { und } \mu , \kappa \in A ^ { * } } \end{array} \right.$$

wobei für jede nicht-negative ganze Zahl z der Ausdruck z mod 3 den Rest der ganzzahligen Division von z mit 3 bezeichne und bei Bedarf Zeichen in A als Wörter der Länge 1 in A^{1} aufzufassen sind.

a) Berechnen Sie die Wörter baac \( \odot \) aaaa, baac \( \odot \) bbbbbb und baac \( \odot \) cc

b) Es sei

$$\begin{aligned} \delta : A & \rightarrow A \\ \mathrm { a } & \mapsto \mathrm { a } \\ \mathrm { b } & \mapsto \mathrm { c } \\ \mathrm { c } & \mapsto \mathrm { b } \end{aligned}$$

Geben Sie für jedes \( u \in A ^ { * } \text { ein } v \in A ^ { * } \text { so an, dass } u \odot v = \mathrm { a } ^ { | u | } \).

c) Beweisen Sie durch vollständige Induktion, dass für jedes n ∈ N_{0} gilt:

$$w \in A ^ { n } : w \odot \mathrm { a } ^ { n } = w$$


Bild Mathematik


Quelle: http://gbi.ira.uka.de/aufgaben/blatt-02-aufgaben.pdf

Lösungen: http://gbi.ira.uka.de/aufgaben/blatt-02-loesungen.pdf

Avatar von

Bei dem letztem Buchstabe wenn ich weiter rechne kommt dann y(3) ..was ist das dann für ein Buchstabe ?

Da ja am Ende c O b bleibt und x=c und y = b wäre

1 Antwort

+1 Daumen

baac O bbbb

In der Terminologie der Aufgabe musst du also schauen, was

sind jetzt x , y , μ und κ  ; denn es muss ja die 2. Zeile der Def.

von O benutzt werden, da keines der beiden Wörter leer ist.

Das ist  x=b , y=b   ( sozusagen jeweils der erste Buchstaben der beiden Wörter)

μ=aac    und κ=bbb   (Die Restwörter  ) 

Dann γ(     (γ-1(x)   + γ-1(y) )  mod 3    )   ausrechnen, das wäre

            =   γ ( (1 + 1 )  mod 3 )    =  γ(2) = c. 

Also fängt    baac O bbbb  mit einem c an, und dahinter kommt das

Ergebnis von  aac O bbb.    Also sieht das so aus

baac O bbbb  =  c· (  aac O bbb )

Dazu musst du   aac O bbb  ausrechnen und das geht wieder genauso:

was   sind jetzt x , y , μ und κ  ?    

  x=a , y=b  und  μ=ac    und κ=bb Dann  γ(     (γ-1(x)   + γ-1(y) )  mod 3    )   ausrechnen, das wäre

            =   γ ( (0 + 1 )  mod 3 )    =  γ(1) = b. 

Also    aac O bbb  =    b· (  ac O bb )   und damit hast du die eigentliche

Aufgabe schon mal so weit:

baac O bbbb  =  cb· (  ac O bb ).

Jetzt  ac O bb  ausrechnen etc.   Da die Wörter in der Klammer immer kürzer

werden hast du irgendwann ein leeres Restwort und dann ist ja  uOv das erste Wort,

nämlich u.     Viel Erfolg beim Weiterrechnen !
Avatar von

Bei dem letztem Buchstabe wenn ich weiter rechne kommt dann y(3) ..was ist das dann für ein Buchstabe ?

Da ja am Ende c O b bleibt und x=c und y = b wäre

dann y(3) ..was

Dann hast du das mod 3 vergessen 

3  mod 3  = 0 , also ist es ein a.


Ein anderes Problem?

Stell deine Frage

Willkommen bei der Stacklounge! Stell deine Frage einfach und kostenlos

x
Made by a lovely community