Formale Sprachen

Einführende Begriffe

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

Definition

Eine formale Sprache LL ist eine beliebige Teilmenge der Kleeneschen Hülle ihres Alphabets Σ\Sigma:
L⊆Σ∗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. CC sind formale Sprache. Die Wörter von CC sind die jeweiligen Programme. Das Alphabet von CC sind die Schlüsselwörter und Zeichen, die in der Definition von CC festgelegt sind.
  • Die natürlichen Zahlen in unärer Darstellung: Nun:={ε,1,11,111,1111,…}\mathbb{N}_{\rm un} := \{\varepsilon,1,11,111,1111,\ldots \}
  • Die unäre Sprache über {a}\{a\}, die nur Wörter quadratischer Länge enthält: {a(n2)∣n∈N}\{ a^{(n^2)} | n\in\mathbb N\}
  • {anbn∣n∈N} \{ a^nb^n | n\in\mathbb N\} für Σ={a,b}\Sigma=\{a,b\}
  • {anbncn∣n∈N}\{ a^nb^nc^n | n\in\mathbb N\} für Σ={a,b,c}\Sigma=\{a,b,c\}

Operationen auf formalen Sprachen

Zwei Sprachen L1L_1 über dem Alphabet Σ1\Sigma_1 und L2L_2 über dem Alphabet Σ2\Sigma_2 sind ebenfalls Spracheen über dem Alphabet Σ1∪Σ2\Sigma_1 \cup \Sigma_2, also Mengen von Worten aus (Σ1∪Σ2)∗(\Sigma_1 \cup \Sigma_2)^*. Deshalb sind auch
Sprachen über Σ1∪Σ2\Sigma_1 \cup \Sigma_2.

Konkatenation

Die Konkatenation zweier Sprachen L1L_1 und L2L_2 ist die Sprache der Wörter, die durch Hintereinanderschreibung (Konkatenation) je eines beliebigen Wortes uu aus L1L_1 und vv aus L2L_2 entsteht:
L1∘L2:={uv∣u∈L1,v∈L2}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 Σ={a, b}\Sigma = \lbrace a ,\, b \rbrace:
{a}∘{ab}={aab}\lbrace a \rbrace \circ \lbrace ab \rbrace = \lbrace aab \rbrace
{a, bb}∘{aa, b}={aaa, ab, bbaa, bbb}\lbrace a ,\, bb \rbrace \circ \lbrace aa ,\, b \rbrace = \lbrace aaa ,\, ab ,\, bbaa ,\, bbb \rbrace
{abb, bab}∘{ε, aab, bb}={abb, bab, abbaab, babaab, abbbb, babbb}\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 LL:
L∘{ε}={ε}∘L=LL \circ \lbrace \varepsilon \rbrace = \lbrace \varepsilon \rbrace \circ L = L
Das absorbierende Element der Konkatenation ist die leere Sprache, sodass für jede Sprache L⊆Σ∗L \subseteq \Sigma^* gilt:
L∘{}={}∘L={}L \circ \{ \} = \{ \} \circ L = \{ \}
Die Konkatenation von Sprachen ist wie die Konkatenation von Wörtern assoziativ, aber nicht kommutativ. So ist zum Beispiel:
({a, bab} ∘ {a, b}) ∘ {ab}={a, bab} ∘ ({a, b} ∘ {ab})={aaab, abab, babaab, babbab}(\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:
{a, bab} ∘ {a, b}={aa, ab, baba, babb}¬={aa, abab, ba, bbab}={a, b} ∘ {a, bab}\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 Σ\Sigma (die gleich der Menge aller Sprachen ist, die aus Σ\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 LnL^n einer Sprache ist die nn-fache Konkatenation dieser Sprache mit sich selbst. Sie ist rekursiv definiert mit:
L0:={ε}L^0 := \{\varepsilon\}
Ln+1:=Ln∘LL^{n+1} := L^n \circ L (für n∈N0n \in \mathbb{N}_0)
So sind zum Beispiel:
{aa, abab, bbab, ba}0={ε}\lbrace aa ,\, abab ,\, bbab ,\, ba \rbrace^0 = \lbrace \varepsilon \rbrace
{a, b}2={a, b}1 ∘ {a, b}=({a, b}0 ∘ {a, b}) ∘ {a, b}=({ε} ∘ {a, b}) ∘ {a, b}={aa, ab, ba, bb}\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
{a}4={a} ∘ {a} ∘ {a} ∘ {a}={aaaa}\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 L={w}L = \lbrace w \rbrace (mit w∈Σ∗w \in \Sigma^\ast ) und jedes n∈N0n \in \mathbb{N}_0:
Ln={w}n={wn}L^n = \lbrace w \rbrace^n = \lbrace w^n \rbrace

Kleene-*-Abschluss und Kleene-+-Abschluss

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

Strukturen sind die Waffen der Mathematiker.

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е
Datenschutzerklärung

 

Informatik