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}L\_0$​ und $L_{1}L\_1$​ gilt

$L_0\cup L_1=\{x\mid x\in L_0\vee x\in L_1\}L\_0\; \backslash cup\; L\_1\; ~=~\; \backslash \{x\; \backslash mid\; x\; \backslash in\; L\_0\; \backslash vee\; x\; \backslash in\; L\_1\backslash \}$

Die Vereinigung der Sprachen $L_{0}L\_0$ und $L_{1}L\_1$ besteht also aus allen Wörtern $xx$, die in der Sprache $L_{0}L\_0$ oder in der Sprache $L_{1}L\_1$ enthalten sind (oder in beiden).

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

$L_0\cup L_1=L\_0\; \backslash cup\; L\_1\; =$ {aa, ab, aba, abba}

Verkettung

Die Verkettung (auch das Produkt) $L_0{L}_{1}L\_0L\_1$ zweier formaler Sprachen $L_{0}L\_0$ und $L_{1}L\_1$​ erhältst du, indem du jedes Wort $xx$ aus der Sprache $L_{0}L\_0$ mit jedem Wort $yy$ aus der Sprache $L_{1}L\_1$ verkettest:

$L_0{L}_1=\{xy\mid x\in L_0,y\in L_1\}L\_0L\_1\; ~=~\; \backslash \{xy\; \backslash mid\; x\; \backslash in\; L\_0,~\; y\; \backslash in\; L\_1\backslash \}$

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

Wenn zum Beispiel die Sprache $L_0=L\_0\; =$ {a, le} ist und die Sprache $L_1=L\_1\; =$ {ber, bend, der}, was ist dann die Sprache $L_0{L}_{1}L\_0L\_1$? Du verkettest einfach jedes Wort aus $L_{0}L\_0$ mit jedem Wort aus $L_{1}L\_1$ und erhältst die Sprache

$L_0{L}_1=L\_0L\_1\; =$ {aber, abend, ader, leber, lebend, leder}

Potenz

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

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

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

Allgemein gilt für eine beliebige Sprache $LL$

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

Abschluss

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

$L^{\ast }=L^0\cup L^1\cup L^2\cup L^3\cup \dots L^*\; ~=~\; L^0\; \backslash cup\; L^1\; \backslash cup\; L^2\; \backslash cup\; L^3\; \backslash cup\; \dots$

Wenn beispielsweise Sprache $LL$ = {bla} gegeben ist, wie lautet die Sprache $L^{\ast }L^*$ ? Du verkettest die Sprache $LL$ 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}L^0,\; L^1,\; L^2,\; L^3$ usw. Das Ergebnis ist

$L^{\ast }=L^*\; =$ {$\epsilon \backslash 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 $\mathrm{\varnothing }\backslash empty$ eine Sprache ist. Überlege dir Folgendes:

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

$\mathrm{\varnothing }\cup L=L\backslash empty\; \backslash cup\; L\; =\; L$

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

$\mathrm{\varnothing }L=\mathrm{\varnothing }\backslash empty\; L\; =\; \backslash empty$

Wenn die Sprache $LL$ ebenfalls die leere Menge ist, ergibt sich ${\mathrm{\varnothing }}^2=\mathrm{\varnothing }\backslash empty^2\; =\; \backslash empty$. Damit gilt natürlich auch ${\mathrm{\varnothing }}^3=\mathrm{\varnothing }\backslash empty^3\; =\; \backslash empty$ usw. Alle Potenzen der leeren Menge ergeben also die leere Menge.

Wirklich alle Potenzen? Welche Sprache ist ${\mathrm{\varnothing }}^0\backslash emptyset^0$ ? Schau noch einmal in der Definition nach. Dort siehst du, dass ${\mathrm{\varnothing }}^0=\{\epsilon \}\backslash empty^0\; =\; \backslash \{\backslash varepsilon\backslash \}$ ist, also die Sprache, die nur aus dem leeren Wort $\epsilon \backslash 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 $\mathrm{\varnothing }\backslash empty$ und der Menge $\{\epsilon \}\backslash \{\backslash varepsilon\; \backslash \}$, denn die eine Menge enthält 0 Elemente und die andere 1 Element.

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

Natürlich sind dies alles Spitzfindigkeiten. Die Anschauung versagt, wenn du sagen sollst, welche Sprache ${\mathrm{\varnothing }}^{\ast }\backslash 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.