Listen Sie alle w ∈ Σ* auf, für die gilt: w R+1611161166

Question

a) Sei Σ = {1,6} und Σ^* die Menge alles aus Σ bildbaren Worte, also aller Zahlen, die nur die Ziffern 1 und 6 enthalten (inkl. dem leeren Wort " ").

Aus wie vielen Worten mit genau 9 Zeichen besteht Σ^* ? A: 512

Aus wie vielen Worten mit max. 9 Zeichen besteht Σ^* ? A: 1023

b) Auf Σ^* aus (a) wird nun eine Relation R definiert: Ein Wort w ∈ Σ^* stehe in Relation zu den Worten w6 und w11.

Liste Sie alle w ∈ Σ^* auf, für die gilt: 16 R² w:

A: { 1666; 161111; 16611; 16116 }

c) Betrachtet wird weiter die Relation R aus (b).

Listen Sie alle w ∈ Σ^* auf, für die gilt: w R⁺1611161166: {?}

Hier komme ich leider nicht mehr weiter.

Comments

Es gilt

161 R 16111 R 161116 R 16111611 R 161116116 R 1611161166

---

Wie bist du darauf gekommen?

Und ich glaube, es fehlt noch eins

---

Du kannst "nach links" von hinten entweder eine 6 streichen oder eine 11.

Was denkst du welches Wort noch fehlt?

---

"Gefehlt" hat tatsächlich gar keins, der hat mir das dennoch als Fehler anzeigt, weil 1611161166 selbst enthalten war.

Danke!

---

Achso. Als Menge ist es natürlich nur

{ 161, 16111, 161116, 16111611, 161116116 }

Die Relation ist nicht reflexiv. Die transitive Hülle funktioniert ja so:

Es gilt

x R⁺ y

genau dann wenn ein Pfad/Weg

\(x~ R~ z_1~ R~ ...~ R ~z_n ~R~ y \)

mit \( n\in\mathbb N_0\) existiert (für n=0 dann eben ohne "Mittelteil")