Wörter, Alphabete und Mengen

04.11.2008, 14:42

prinzschleifer

Wörter, Alphabete und Mengen

Hallo!

Vorneweg: Ich bin mir nicht sicher ob das hier das richtige Forum ist. Aber ich brauche mal wieder Hilfe:

Gegeben ist das Alphabet $\begin{eqnarray*} A= \left\{a,b\right\} \end{eqnarray*}$ . Eine Folge $\begin{eqnarray*} L_0,L_1,... \end{eqnarray*}$

Ferner gilt: $\begin{eqnarray*} L_0= \left\{ \varepsilon \right\} \end{eqnarray*}$

$\begin{eqnarray*} \forall n \in \mathbb N_0 : L_{n+1} = L_n \cup \left\{ a\gamma b | \gamma \in L_n \right\} \end{eqnarray*}$

So nun soll man das $\begin{eqnarray*} L_1 \end{eqnarray*}$ berechnen:

Dazu:
n:=0
$\begin{eqnarray*} L_{1} = L_0 \cup \left\{ a\gamma b | \gamma \in L_0 \right\} \end{eqnarray*}$

$\begin{eqnarray*} L_{1} =\left\{ \varepsilon \right\} \cup \left\{ a\gamma b | \gamma \in L_0 \right\} \end{eqnarray*}$

Gut jetzt kommen erste Verständnisschwierigkeiten. Wenn $\begin{eqnarray*} \gamma \in L_0 \end{eqnarray*}$ heißt das das $\begin{eqnarray*} \gamma = \varepsilon \end{eqnarray*}$ ist?

Das heißt:
$\begin{eqnarray*} L_{1} = \left\{ \varepsilon \right\} \cup \left\{ a\varepsilon b\right\} \end{eqnarray*}$

$\begin{eqnarray*} L_{1} = \left\{ \varepsilon , a\varepsilon b\ \right\} \end{eqnarray*}$

Stimmt dieser Ansatz?

04.11.2008, 15:00

papahuhn

Auf diesen Beitrag antworten »

Ja, wobei man $\begin{eqnarray*} a \varepsilon b \end{eqnarray*}$ noch vereinfachen kann.

04.11.2008, 15:08

prinzschleifer

Auf diesen Beitrag antworten »

Also so:

$\begin{eqnarray*} L_{1} = \left\{ \varepsilon , ab\ \right\} \end{eqnarray*}$ ?
Da es sich hier ja um eine Konkatenation handelt, kann man das neutrale Element zwischen den beiden Zeichen weglassen. Das leere Wort am Anfang der Menge aber nicht?

Gut, nun mach ich das Probehalber mal für $\begin{eqnarray*} L_2 \end{eqnarray*}$
$\begin{eqnarray*} L_{2} = L_1 \cup \left\{ a\gamma b | \gamma \in L_1 \right\} \end{eqnarray*}$

Jetzt steht hier das $\begin{eqnarray*} \gamma \in L_1 \end{eqnarray*}$ . Nun weiß ich nicht, wie diese Menge aussieht: $\begin{eqnarray*} \left\{ a\gamma b | \gamma \in L_1 \right\} \end{eqnarray*}$

Müsste es dann sowas sein?
$\begin{eqnarray*} \left\{ a\gamma b | \gamma \in L_1 \right\} = \left\{ a\varepsilon b, aabb\right\} \end{eqnarray*}$ ?

Da steht ja nur das das $\begin{eqnarray*} \gamma \in L_1 \end{eqnarray*}$ , aber zu welchem Element in der Menge nicht. Ich bin verwirrt.

04.11.2008, 15:28

papahuhn

Auf diesen Beitrag antworten »

Zitat:

Original von prinzschleifer
Also so:

$\begin{eqnarray*} L_{1} = \left\{ \varepsilon , ab\ \right\} \end{eqnarray*}$ ?
Da es sich hier ja um eine Konkatenation handelt, kann man das neutrale Element zwischen den beiden Zeichen weglassen. Das leere Wort am Anfang der Menge aber nicht?

Ja, auch wenn es keine Zeichen im leeren Wort gibt, möchte man sehen, worüber man redet. Das ist also Vereinbarungssache. Analog dazu schreibst du für die Zehn "10" und nicht "0010", aber für die Null schreibst du "0" und nicht nichts.

Zitat:

Original von prinzschleifer
Da steht ja nur das das $\begin{eqnarray*} \gamma \in L_1 \end{eqnarray*}$ , aber zu welchem Element in der Menge nicht. Ich bin verwirrt.

Zu allen Elementen.

04.11.2008, 15:40

prinzschleifer

Auf diesen Beitrag antworten »

Also ist $\begin{eqnarray*} L_2 = \left\{ ab , \varepsilon , aabb , a\varepsilon b \right\} \end{eqnarray*}$ ?

Ach verstehe, sorry:
Also ist $\begin{eqnarray*} L_2 = \left\{ ab , \varepsilon , aabb \right\} \end{eqnarray*}$

Das ganze müssen wir jetzt explizit darstellen ohne Beweis. Ich mach mich dann mal ran.

04.11.2008, 15:44

papahuhn

Auf diesen Beitrag antworten »

Im Prinzip ja, aber du hast wieder nicht vereinfacht.

04.11.2008, 15:59

prinzschleifer

Auf diesen Beitrag antworten »

Die Frage nach des Beweises ist recht seltsam formuliert:
Geben Sie für beliebieges $\begin{eqnarray*} n \in \mathbb N_0 \end{eqnarray*}$ eine explizite Formel für $\begin{eqnarray*} L_n \end{eqnarray*}$ an, in der nicht irgendwelche $\begin{eqnarray*} L_i \end{eqnarray*}$ vorkommen.

$\begin{eqnarray*} L_i \end{eqnarray*}$ ist nicht weiter spezifiziert. Leider ist in jeder Menge von $\begin{eqnarray*} L_i \end{eqnarray*}$ immer die leere Menge drin, bzw. das Element ab, also gibt es ein solches $\begin{eqnarray*} L_i \end{eqnarray*}$ nicht oder versteh ich die Frage falsch?

04.11.2008, 16:27

papahuhn

Auf diesen Beitrag antworten »

Du sollst eine Gleichung der Form $\begin{eqnarray*} L_n = ... \end{eqnarray*}$ aufstellen, in der auf der rechten Seite keine $\begin{eqnarray*} L_\text{irgendwas} \end{eqnarray*}$ auftauchen.
z.B. ist $\begin{eqnarray*} L_3 = \{\varepsilon, a^1b^1, a^2b^2, a^3b^3\} \end{eqnarray*}$ .

04.11.2008, 17:43

prinzschleifer

Auf diesen Beitrag antworten »

Mhh, also ich weiß jetzt nicht wie man das mit Mengen schreibt, aber ich probiers mal:

$\begin{eqnarray*} L_n = \bigcup^{n}_{k=1}a^k b^k \cup \{ \varepsilon \} \end{eqnarray*}$

So? Oder ist das kompletter Unfug?

04.11.2008, 18:13

papahuhn

Auf diesen Beitrag antworten »

Sieht doch schonmal sehr gut aus. Du kannst das noch kompakter schreiben, indem du den Index k ab 0 laufen lässt und die rechte Menge weglässt.

04.11.2008, 18:32

prinzschleifer

Auf diesen Beitrag antworten »

Ah okay, vielen dank!

Ich war mir nur unsicher, ob $\begin{eqnarray*} a^0 b^0 = \varepsilon \varepsilon = \varepsilon \end{eqnarray*}$ ist. Aber anscheined ist es ja so.

Vielen vielen Dank!

Neue Frage »

Antworten »

Wörter, Alphabete und Mengen

Verwandte Themen