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 L0​ und L1​ gilt

L0L1 = {x|xL0xL1}

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

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

L0L1= {aa, ab, aba, abba}

Verkettung

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

L0L1 = {xy|xL0, yL1}

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

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

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

L2= {aa, ale, lea, lele}

Allgemein gilt für eine beliebige Sprache L

Ln = {{ε}falls n=0Ln1Lsonst

Es ist also Ln=LLL... (n-mal). Offenbar gilt L1=L. Wichtig ist auch, dass L0={ε} ist.

Abschluss

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

L = L0L1L2L3

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 L0,L1,L2,L3 usw. Das Ergebnis ist

L= {ε, 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 eine Sprache ist. Überlege dir Folgendes:

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

L=L

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

L=

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

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

Nachdem du weißt, dass 0={ε} ist, kannst du auch die Sprache bilden. Schau in der Definition nach.

Natürlich sind dies alles Spitzfindigkeiten. Die Anschauung versagt, wenn du sagen sollst, welche Sprache 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

Laden

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?