Nachdem wir Wörter und Alphabete formal definiert haben können wir uns von diesen einen Schritt weiter bewegen und formale Sprachen kennenlernen. Flapsig gesagt sind formale Sprachen Teilmengen von Wörtern über einem Alphabet. Wie man so etwas genau definieren kannst du im folgenden nachlesen.

Definition

Eine formale Sprache %%L%% über einem Alphabet %%A%% ist eine Teilmenge %%L\subset A^*%%. Dabei steht %%A^*%% für alle Wörter die mit Buchstaben aus dem Alphabet %%A%% gebildet werden können. So ist eine mögliche formale Sprache über dem Alphabet %%A = \{a,b\}%% die Sprache %%L=\{a,ab,abbba\}%%.

Operationen auf formalen Sprachen

Genau wie zuvor auch bei Alphabeten kann man auch auf formalen Sprachen Operationen ausführen.

  • Produkt: Das Produkt zweier formaler Sprachen ist so definiert, dass man jedes Wort aus der ersten formalen Sprache mit jedem Wort aus der zweiten formalen Sprache konkateniert.
  • Der Konkatenationsabschluss: der Konkatenationsabschluss einer formalen Srpache ist %%A^*%% sehr ähnlich. Der Konkatenationsabschluss einer formalen Sprache wird auch mit %%L^*%% bezeichnet und heißt soviel wie, dass man %%L%% beliebig oft mit sich selbst multipliziert.
  • Der %%\epsilon%%-freie Konkatenationsabschluss: Der %%\epsilon%%-freie Konkatenationsabschluss ist genauso definiert wie der normale Konkatenationabschluss einer formalen Sprahce. Der einzige Unterschied liegt darin, das hier der Fall %%L^0 = \{\epsilon\}%% ausgeschlossen wird. Dies bezeichnet man dann als %%L^+%%.
  • *

Anwendung am Beispiel:

  • Sei %%L_1=\{a,b\}%%. Dann ist %%L_1^* = \{\epsilon, a,b,ab,ba,aa,bb,aab,..\}%%.Wichtig ist hierbei, dass die hieraus entstehende Menge unendlich ist.
  • Sei %%L_2 = \{a^nb^n|n\in\mathbb{N}\}%%. Dann ist %%L_2%% die Menge die nur aus Wörtern mit n mal dem Buchstaben a, auf den genau n mal der Buchstabe b folgt besteht.
Kommentieren Kommentare