Springe zum Inhalt oder Footer
SerloDie freie Lernplattform

Operationen auf Sprachen

Es gibt drei wichtige Operationen, die du auf Sprachen anwenden kannst: Vereinigung, Verkettung und Abschluss.

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 L0L_0​ und L1L_1​ gilt

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

Die Vereinigung der Sprachen L0L_0 und L1L_1 besteht also aus allen Wörtern xx, die in der Sprache L0 L_0 oder in der Sprache L1L_1 enthalten sind (oder in beiden).

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

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

Verkettung

Die Verkettung (auch das Produkt) L0L1L_0L_1 zweier formaler Sprachen L0 L_0 und L1 L_1 ​ erhältst du, indem du jedes Wort xx aus der Sprache L0L_0 mit jedem Wort yy aus der Sprache L1L_1 verkettest:

L0L1 = {xyxL0, yL1}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 L0=L_0 = {a, le} ist und die Sprache L1=L_1 = {ber, bend, der}, was ist dann die Sprache L0L1L_0L_1? Du verkettest einfach jedes Wort aus L0L_0 mit jedem Wort aus L1L_1 und erhältst die Sprache

L0L1=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 L2=LLL^2 = LL aus? Du verkettest jedes Wort der Sprache LL mit jedem Wort der Sprache LL und erhältst

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

Allgemein gilt für eine beliebige Sprache LL

Ln = {{ε}falls n=0Ln1Lsonst\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 Ln=LLL...L^n = LLL... (nn-mal). Offenbar gilt L1=LL^1 = L. Wichtig ist auch, dass L0={ε}L^0 = \{\varepsilon\} ist.

Abschluss

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

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

Wenn beispielsweise Sprache LL = {bla} gegeben ist, wie lautet die Sprache LL^* ? 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 L0,L1,L2,L3L^0, L^1, L^2, L^3 usw. Das Ergebnis ist

L=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 L\empty \cup L bildest, wobei LL irgendeine Sprache ist? Du fasst alle Wörter, die in der Sprache \empty vorkommen (also keine) oder die in der Sprache LL vorkommen, zu einer neuen Sprache zusammen und erhältst natürlich dann

L=L\empty \cup L = L

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

L=\empty L = \empty

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

Wirklich alle Potenzen? Welche Sprache ist 0\emptyset^0 ? Schau noch einmal in der Definition nach. Dort siehst du, dass 0={ε}\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 0={ε}\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.

Übungsaufgaben: Operationen auf Sprachen

Du hast noch nicht genug vom Thema?

Hier findest du noch weitere passende Inhalte zum Thema:

Artikel


Dieses Werk steht unter der freien Lizenz
CC BY-SA 4.0Was bedeutet das?