Operationen auf Sprachen

Schau dir als Erstes die Definitionen dieser drei Operationen an. Danach findest du Beispiele, an denen du noch einmal die Definitionen nachvollziehen kannst.

Vereinigung

Sprachen sind Mengen (von Wörtern), und Mengen lassen sich mit der Mengenoperation Vereinigung vereinigen. Für zwei Sprachen $L_0$​ und $L_1$​ gilt

$L_0 \cup L_1 ~=~ \{x \mid x \in L_0 \vee x \in L_1\}$

Die Vereinigung der Sprachen $L_0$ und $L_1$ besteht also aus allen Wörtern $x$, die in der Sprache $L_0$ oder in der Sprache $L_1$ enthalten sind (oder in beiden).

Betrachte als Beispiel die Sprachen $L_0$ = {ab, aba} und $L_1$ = {aa, aba, abba}. Du bildest die Vereinigung der beiden Sprachen, indem du alle Wörter, die in der Sprache $L_0$ vorkommen oder die in der Sprache $L_1$ vorkommen (oder in beiden) zu einer neuen Sprache zusammenfasst:

$L_0 \cup L_1 =$ {aa, ab, aba, abba}

Verkettung

Die Verkettung (auch das Produkt) $L_0L_1$ zweier formaler Sprachen $L_0$ und $L_1$​ erhältst du, indem du jedes Wort $x$ aus der Sprache $L_0$ mit jedem Wort $y$ aus der Sprache $L_1$ verkettest:

$L_0L_1 ~=~ \{xy \mid x \in L_0,~ y \in L_1\}$

Zwei Wörter verkettest du, indem du sie einfach hintereinander schreibst.

Wenn zum Beispiel die Sprache $L_0 =$ {a, le} ist und die Sprache $L_1 =$ {ber, bend, der}, was ist dann die Sprache $L_0L_1$? Du verkettest einfach jedes Wort aus $L_0$ mit jedem Wort aus $L_1$ und erhältst die Sprache

$L_0L_1 =$ {aber, abend, ader, leber, lebend, leder}

Potenz

Ein Spezialfall der Verkettung von Sprachen ist die Potenz einer Sprache $L$, also die (mehrfache) Verkettung der Sprache $L$ mit sich selbst.

Wenn zum Beispiel die Sprache $L =$ {a, le} ist, was sieht dann die Sprache $L^2 = LL$ aus? Du verkettest jedes Wort der Sprache $L$ mit jedem Wort der Sprache $L$ und erhältst

$L^2 =$ {aa, ale, lea, lele}

Allgemein gilt für eine beliebige Sprache $L$

$\def\arraystretch{1.25} L^n ~=~ \left\{ \begin{array}{ll}\{\varepsilon \} & \mathrm{falls}~ n = 0 \\ L^{n-1}L & \mathrm{sonst} \end{array} \right.$

Es ist also $L^n = LLL...$ ($n$-mal). Offenbar gilt $L^1 = L$. Wichtig ist auch, dass $L^0 = \{\varepsilon\}$ ist.

Abschluss

Den Abschluss $L^*$ einer Sprache $L$ erhältst du, indem du alle Potenzen der Sprache $L$ miteinander vereinigst:

$L^* ~=~ L^0 \cup L^1 \cup L^2 \cup L^3 \cup …$

Wenn beispielsweise Sprache $L$ = {bla} gegeben ist, wie lautet die Sprache $L^*$ ? Du verkettest die Sprache $L$ jeweils 0-mal, 1-mal, 2-mal, 3-mal usw. mit sich selbst und bildest die Vereinigung aller dieser Potenzen $L^0, L^1, L^2, L^3$ usw. Das Ergebnis ist

$L^* =$ {$\varepsilon$, bla, blabla, blablabla, ...}

Spezialfälle

Am besten verstehst du eine Sache, wenn du auch mit Spezialfällen klarkommst. Du weißt, dass auch die leere Menge $\empty$ eine Sprache ist. Überlege dir Folgendes:

Was passiert, wenn du die Vereinigung $\empty \cup L$ bildest, wobei $L$ irgendeine Sprache ist? Du fasst alle Wörter, die in der Sprache $\empty$ vorkommen (also keine) oder die in der Sprache $L$ vorkommen, zu einer neuen Sprache zusammen und erhältst natürlich dann

$\empty \cup L = L$

Was passiert, wenn du die Verkettung $\empty L$ bildest, wobei $L$ irgendeine Sprache ist? Du verkettest jedes Wort der Sprache $\empty$ (also keins) mit jedem Wort der Sprache $L$. Du bildest also auf diese Weise kein einziges Wort, somit ist

$\empty L = \empty$

Wenn die Sprache $L$ ebenfalls die leere Menge ist, ergibt sich $\empty^2 = \empty$. Damit gilt natürlich auch $\empty^3 = \empty$ usw. Alle Potenzen der leeren Menge ergeben also die leere Menge.

Wirklich alle Potenzen? Welche Sprache ist $\emptyset^0$ ? Schau noch einmal in der Definition nach. Dort siehst du, dass $\empty^0 = \{\varepsilon\}$ ist, also die Sprache, die nur aus dem leeren Wort $\varepsilon$ besteht.

Vielleicht findest du, dass ein Baby, das noch gar kein Wort sprechen kann, und ein Baby, das nur das leere Wort sprechen kann, sich in ihrem Sprachvermögen nicht besonders unterscheiden. Mathematisch besteht aber ein großer Unterschied zwischen der Menge $\empty$ und der Menge $\{\varepsilon \}$, denn die eine Menge enthält 0 Elemente und die andere 1 Element.

Nachdem du weißt, dass $\empty^0 = \{\varepsilon\}$ ist, kannst du auch die Sprache $\empty^*$ bilden. Schau in der Definition nach.

Natürlich sind dies alles Spitzfindigkeiten. Die Anschauung versagt, wenn du sagen sollst, welche Sprache $\empty^*$ ist. Aber wenn du in der Definition nachschaust, dann machen dir auch diese Extremfälle keine ernsthaften Probleme.

Du brauchst die Operationen Vereinigung, Verkettung und Abschluss, um reguläre Ausdrücke zu bilden.