Alphabet-Abb.: bijektiv, Aufgabe

Question

Komme hier einfach nicht weiter:

A sei ein Alphabet
a) Gesucht bijektive Abbildung f: A∗ → A∗, die nicht die identische
Abbildung A∗ → A∗, w |→ w, ist.


b) Gesucht ist Abbildung f: A∗ → A∗, so dass für jedes w ∈ A∗gilt: |f(w)| = 2^|w|· |w|^|w| gilt


c) Gesucht; Abbildung g: 2^A∗→ 2^A∗, so dass für jedes L ∈ 2^A∗ gilt: {|w| | w ∈ h(L)} = {3 · |w| | w ∈ L} gilt

d) Gesucht Abbildung h : 2^A∗→ 2^A∗ , so dass für jedes L ∈ 2^A∗und für jedes w ∈ A∗ gilt:
w ist Element von L genau dann, wenn w nicht Element von h(L).


Habe einfach keine Idee, wie ich diese Aufgabe angehen soll. Danke im Voraus.

Comments

Zu c) Was ist h(L)?

---

L sei eine formale Sprache über A und h ist die Fkt.

zu a) ich habe da bisher : A2->A2  w|=>w²      ?!?

Answer 1

a) Jede bijektive Abbildung auf A induziert eine bijektive Abbildung auf A*.

b) Sei a∈A. Wähle f(w) = a^{2^|w|· |w|^|w|} für jedes w∈A*.

Comments

ok danke. Hast du noch einen Ansatz für die restlichen Teilaufgaben, weil da komme ich einfach nicht voran...

---

Was ist 2^A∗?

---

Potenzmenge von A*

---

c) Sei a∈A.  h : L ↦ {a^3|w| | w∈L}

d) h: L ↦ A*\L

---

Danke erstmal. werde mich jetzt mal durch Deine Lsg. durcharbeiten und die Unterschiede in meinen Ansätzen versuchen zu verstehen.

---

Habe deine Lsg. verstanden, nun aber diesbezüglich zwei weitere Fragen:

Wenn ich nun eine Abb. f: A^*=>A^* suche, die nicht surjektiv, aber injektiv ist, ist w=>{a in A|f(a)=w|w in A^*) eine Lösung?

bzw. ist für eine Abb. g: A^*=> A^* w=>{a in A|g(a)=w^2|w in A*} eine Lösung, wenn nach einer surjektiven, aber nicht injektiven Abb. gefragt werden würde?

Gibt es noch andere Bsp.?

Vielen Dank im Voraus.

---

> f: A^*=>A^* ...  ist w=>{a in A|f(a)=w|w in A^*) eine Lösung

Nein.

{a in A|f(a)=w|w in A^*) ist kein Element von A^*, also kann w=>{a in A|f(a)=w|w in A^*) keine Abbildungsvorschrift für eine Abbildung von  A^* nach A^* sein.

> ist für eine Abb. g: A^*=> A^* w=>{a in A|g(a)=w²|w in A*}...

g ist keine Abbildung, weil {a in A|g(a)=w²|w in A*} kein Element von A^* ist. Fragen nach Surjektivität und Injektivität erübrigen sich daher.

---

Danke. Aber was sind dann Bsp. für Typ a) und Typ b)? Weiss nicht wie ich stichhaltig ein Bsp. finde!?

---

Zu a) Ein Bsp kann man erst dann konstruieren, wenn ein konkretes Alphabet A vorliegt. So lange das nicht der Fall ist, kann man nur abstrakt argumentieren, dass jede bijektive Abbildung auf A eine bijektive Abbildung auf A* induziert.

Zu b) Ein Bsp kann man erst dann konstruieren, wenn ein konkretes Alphabet A vorliegt und aus diesem ein konkretes a ausgewählt wurde. So lange das nicht der Fall ist, kann man nur abstrakt argumentieren, dass die Abbildungsvorschrift w ↦ a^{2^|w|· |w|^|w|} die Anforderungen aus b) erfüllt.

---

Sorry hatte mich nicht eindeutig ausgedrückt, aber jetzt wurde es mir dennoch noch etw. klarer.Danke.

Meinte eigtl. ein Bsp. fuer injektiv, aber nicht surjektiv und umgekehrt, da es für mich gerade etw. schwierigist eine Vorschrift fuer z.B. eine linkseindeutige, aber nicht surjektiv Abb. bzgl. A^* und w zu formulieren.

---

Kannst du mir diesbzgl. bitte auf die Sprünge helfen? Danke schon mal.

---

Injektiv aber nicht surjektiv: Das Wort a₁a₂...a_n wird abgebildet auf a₁a₁a₂a₂...a_na_n.

Surjektiv aber nicht injektiv: Nimm die Abbildung, die von jedem Wort den ersten Buchstaben entfernt.

---

Danke,

Also dann: w=> {a in A | f(a) = Vereinigung von i=1 ueber n von wi und dann noch wn  , n in N

Wie schreibe ich das fuer die Konkatenation?

Undd dann :

wn-1wn => wn  ?!

Vielen Dank nochmals

---

Könnte ich ersteres auch als

w=> w^{n+1} n in N0 schreiben?

---

a₁a₂...a_n ↦ a₁a₁a₂a₂...a_na_n ist nicht da gleiche wie w=> wⁿ⁺¹ n in N0

Übrigens: => ist ein Folgerungspfeil. A => B sagt "Wenn die Aussage A wahr ist, dann, ist die Aussage B auch wahr.

Im Zusammenhang mit Abbildung sind die Pfeile → und ↦ interessant. A → B besagt: "Definitionsmenge der Abbildung ist A, Zielmenge der Abbildung ist B". A ↦ B besagt: "Das Element A der Definitionsmenge wird auf das Element B der Zielmenge abgebildet". Bitte verwende diese Zeichen. Du findest sie in der Symbolleiste wenn du die Schaltfläche Ω betätigst.

---

Alles klar. Aber wie kann ich nun das ganze ohne "..." schreiben, komme nicht auf die induktive Definition.

Ginge auch L sei Teilmenge von A*

A^* →A^*    L^n ↦L^n * w^n ?!

---

Du brauchst es nicht ohne "..." zu schreiben. Es würde es auch nur unverständlicher machen:

w ↦ w' so dass ∀i∈[1,|w|]∩ℕ w'_2i-1=w'_2i=w_i. Dabei ist mit w_i der Buchstabe an der Stelle i des Wortes w gemeint.