Formale Sprachen

Einführende Begriffe

Sei \(\displaystyle \Sigma\) eine endliche Menge von Symbolen, diese nennen wir auch Alphabet.
Ein Wort \(\displaystyle w\) der Länge \(\displaystyle n\) ist dann eine beliebige Teilmenge des \(\displaystyle n\)-fachen kartesischen Produkts \(\displaystyle \Sigma^n\), also
\(\displaystyle w\) ist Wort genau dann wenn \(\displaystyle w\in\Sigma^n\).
Für den Spezialfall \(\displaystyle n=0\) definieren wir das leere Wort \(\displaystyle \epsilon\).
Die Menge aller Wörter wird auch Kleenesche Hülle genannt und mit \(\displaystyle \Sigma^*\) bezeichnet, also
\(\displaystyle \Sigma^*=\bigcup\limits_{n\in\N }\Sigma^n\).
 
 

Definition

Eine formale Sprache \(\displaystyle L\) ist eine beliebige Teilmenge der Kleeneschen Hülle ihres Alphabets \(\displaystyle \Sigma\):
\(\displaystyle L \subseteq \Sigma^*\).
Formale Sprachen können leer, endlich oder unendlich sein, maximal können sie die gesamte Kleenesche Hülle ihres Alphabetes umfassen.
Die in der theoretischen Informatik auftretenden Sprachen sind jedoch meistens sehr speziell und werden durch bestimmte Ersetzungsverfahren definiert, die als formale Grammatiken bezeichnet werden.

Beispiele

  • Programmiersprachen wie z.B. \(\displaystyle C\) sind formale Sprache. Die Wörter von \(\displaystyle C\) sind die jeweiligen Programme. Das Alphabet von \(\displaystyle C\) sind die Schlüsselwörter und Zeichen, die in der Definition von \(\displaystyle C\) festgelegt sind.
  • Die natürlichen Zahlen in unärer Darstellung: \(\displaystyle \mathbb{N}_{\rm un} := \{\varepsilon,1,11,111,1111,\ldots \}\)
  • Die unäre Sprache über \(\displaystyle \{a\}\), die nur Wörter quadratischer Länge enthält: \(\displaystyle \{ a^{(n^2)} | n\in\mathbb N\}\)
  • \(\displaystyle \{ a^nb^n | n\in\mathbb N\}\) für \(\displaystyle \Sigma=\{a,b\}\)
  • \(\displaystyle \{ a^nb^nc^n | n\in\mathbb N\}\) für \(\displaystyle \Sigma=\{a,b,c\}\)

Operationen auf formalen Sprachen

Zwei Sprachen \(\displaystyle L_1\) über dem Alphabet \(\displaystyle \Sigma_1\) und \(\displaystyle L_2\) über dem Alphabet \(\displaystyle \Sigma_2\) sind ebenfalls Spracheen über dem Alphabet \(\displaystyle \Sigma_1 \cup \Sigma_2\), also Mengen von Worten aus \(\displaystyle (\Sigma_1 \cup \Sigma_2)^*\). Deshalb sind auch
Sprachen über \(\displaystyle \Sigma_1 \cup \Sigma_2\).

Konkatenation

Die Konkatenation zweier Sprachen \(\displaystyle L_1\) und \(\displaystyle L_2\) ist die Sprache der Wörter, die durch Hintereinanderschreibung (Konkatenation) je eines beliebigen Wortes \(\displaystyle u\) aus \(\displaystyle L_1\) und \(\displaystyle v\) aus \(\displaystyle L_2\) entsteht:
\(\displaystyle L_1 \circ L_2 := \{ uv | u \in L_1, v \in L_2 \}\).
So sind zum Beispiel die Konkatenationen von verschiedenen Sprachen über dem Alphabet \(\displaystyle \Sigma = \lbrace a ,\, b \rbrace\):
\(\displaystyle \lbrace a \rbrace \circ \lbrace ab \rbrace = \lbrace aab \rbrace\)
\(\displaystyle \lbrace a ,\, bb \rbrace \circ \lbrace aa ,\, b \rbrace = \lbrace aaa ,\, ab ,\, bbaa ,\, bbb \rbrace \)
\(\displaystyle \lbrace abb ,\, bab \rbrace \circ \lbrace \varepsilon ,\, aab ,\, bb \rbrace = \lbrace abb ,\, bab ,\, abbaab ,\, babaab ,\, abbbb ,\, babbb \rbrace\)
Das neutrale Element der Konkatenation ist die Sprache, welche nur das leere Wort enthält. So gilt für jede beliebige Sprache \(\displaystyle L\):
\(\displaystyle L \circ \lbrace \varepsilon \rbrace = \lbrace \varepsilon \rbrace \circ L = L\)
Das absorbierende Element der Konkatenation ist die leere Sprache, sodass für jede Sprache \(\displaystyle L \subseteq \Sigma^*\) gilt:
\(\displaystyle L \circ \{ \} = \{ \} \circ L = \{ \}\)
Die Konkatenation von Sprachen ist wie die Konkatenation von Wörtern assoziativ, aber nicht kommutativ. So ist zum Beispiel:
\(\displaystyle (\lbrace a ,\, bab \rbrace \,\circ\, \lbrace a ,\, b \rbrace) \,\circ\, \lbrace ab \rbrace = \lbrace a ,\, bab \rbrace \,\circ\, (\lbrace a ,\, b \rbrace \,\circ\, \lbrace ab \rbrace) = \lbrace aaab ,\, abab ,\, babaab ,\, babbab \rbrace\)
aber:
\(\displaystyle \lbrace a ,\, bab \rbrace \,\circ\, \lbrace a ,\, b \rbrace = \lbrace aa ,\, ab ,\, baba ,\, babb \rbrace \not= \lbrace aa ,\, abab ,\, ba ,\, bbab \rbrace = \lbrace a ,\, b \rbrace \,\circ\, \lbrace a ,\, bab \rbrace\)
Da außerdem die Potenzmenge der Kleeneschen Hülle eines beliebigen Alphabets \(\displaystyle \Sigma\) (die gleich der Menge aller Sprachen ist, die aus \(\displaystyle \Sigma\) gebildet werden können) abgeschlossen bezüglich Konkatenation ist, bildet sie zusammen mit der Konkatenation als Operator und der Sprache des leeren Wortes als neutrales Element einen Monoiden.

Potenz

Die Potenz \(\displaystyle L^n\) einer Sprache ist die \(\displaystyle n\)-fache Konkatenation dieser Sprache mit sich selbst. Sie ist rekursiv definiert mit:
\(\displaystyle L^0 := \{\varepsilon\}\)
\(\displaystyle L^{n+1} := L^n \circ L\) (für \(\displaystyle n \in \mathbb{N}_0\))
So sind zum Beispiel:
\(\displaystyle \lbrace aa ,\, abab ,\, bbab ,\, ba \rbrace^0 = \lbrace \varepsilon \rbrace\)
\(\displaystyle \lbrace a ,\, b \rbrace^2 = \lbrace a ,\, b \rbrace^1 \,\circ\, \lbrace a ,\, b \rbrace = (\lbrace a ,\, b \rbrace^0 \,\circ\, \lbrace a ,\, b \rbrace) \,\circ\, \lbrace a ,\, b \rbrace = (\lbrace \varepsilon \rbrace \,\circ\, \lbrace a ,\, b \rbrace) \,\circ\, \lbrace a ,\, b \rbrace = \lbrace aa ,\, ab ,\, ba ,\, bb \rbrace\)
\(\displaystyle \lbrace a \rbrace^4 = \lbrace a \rbrace \,\circ\, \lbrace a \rbrace \,\circ\, \lbrace a \rbrace \,\circ\, \lbrace a \rbrace = \lbrace aaaa \rbrace\)
Im Speziellen gilt für jede einelementige, formale Sprache \(\displaystyle L = \lbrace w \rbrace\) (mit \(\displaystyle w \in \Sigma^\ast \)) und jedes \(\displaystyle n \in \mathbb{N}_0\):
\(\displaystyle L^n = \lbrace w \rbrace^n = \lbrace w^n \rbrace\)

Kleene-*-Abschluss und Kleene-+-Abschluss

Der Kleene-*-Abschluss \(\displaystyle L^*\) (auch Iteration genannt) und der Kleene-+-Abschluss \(\displaystyle L^+\) einer formalen Sprache \(\displaystyle L\) sind definiert über die Vereinigung der Potenzsprachen von \(\displaystyle L\):
\(\displaystyle L^* := \bigcup\limits_{i\in\mathbb N_0}L^i\)
\(\displaystyle L^+ := \bigcup\limits_{i\in\mathbb N} L^i\)

Seit der Zeit der Griechen bedeutet "Mathematik" zu sagen, "Beweis" zu sagen.

N. Bourbaki

Copyright- und Lizenzinformationen: Diese Seite basiert dem Artikel Formale Sprache aus der frеiеn Enzyklοpädιe Wιkιpеdιa und stеht unter der Dοppellizеnz GNU-Lιzenz für freie Dokumentation und Crеative Commons CC-BY-SA 3.0 Unportеd (Kurzfassung). In der Wιkιpеdιa ist eine Listе dеr Autorеn des Originalartikels verfügbar. Da der Artikel geändert wurde, reicht die Angabe dieser Liste für eine lizenzkonforme Weiternutzung nicht aus!
Anbieterkеnnzeichnung: Mathеpеdιa von Тhοmas Stеιnfеld  • Dοrfplatz 25  •  17237 Blankеnsее  • Tel.: 01734332309 (Vodafone/D2)  •  Email: cο@maτhepedιa.dе