Eine formale Sprache L über Σ ist eine Teilmenge des Sterns von Sigma.
[ Seitenende ] [ Überkapitel ] [ Bitte Skript-Fehler melden ]
Das Alphabet (Sigma), Zeichen und Zeichenketten
Definition 4.3.1. Ein Alphabet ist eine endliche Menge von Zeichen (atomare Symbole). Es wird mit Σ (Sigma) notiert.
Definition 4.3.2. Eine Zeichenkette (Wort, string) von n Zeichen aus Σ ist eine endliche Folge der Länge n über Σ.
Hinweis zur Notation
Eine Zeichenkette wird typischerweise durch Nebeneinanderschreiben (Juxtaposition) der Zeichen von links nach rechts notiert.
Sei Σ = {a,b}, dann sind etwa 𝜖, a, bb oder ababbba Wörter über Σ.
Stern von Sigma und formale Sprachen
Definition 4.3.3. Der Stern von Sigma ist die Menge aller Wörter über einem Alphabet Σ. Der Stern wird als Postfix-Operator Σ∗ (sprich «Sigma Stern») notiert.
Beispiel 4.3.5. Sei Σ = {a}, dann ist Σ∗ = {𝜖,a,aa,aaa,…}. Die Mengen L1 = {𝜖,a} oder L2 = {aa,aaaa,aaaaaa} sind formale Sprachen, da sie (echte) Teilmengen von Σ∗ sind.
Leere Sprachen vs. leere Zeichenkette
Hinweise
Fragen
Konkatenation von Zeichenketten und Sprachen
Definition 4.3.6. Die Konkatenation von Zeichenketten ist eine zweistellige Funktion, welche ihre Argumente zu einem Wort verkettet. Für alle u,v ∈ Σ∗:
Definition 4.3.7. Die Konkatenation von Sprachen erweitert Verkettung auf Mengen von Zeichenketten. Für alle M,N ⊆ Σ∗:
Eigenschaften der Konkatenation
Zeichenketten
Die Konkatenation ist assoziativ und hat 𝜖 als neutrales Element . Für alle u,v,w ∈ Σ∗:
Sprachen
Die Konkatenation ist assoziativ und hat {𝜖} als neutrales Element . Für alle M,N,P ⊂ Σ∗:
Klammerung
Die Assoziativität der Konkatenation macht Klammern optional.
Stern einer Sprache (Kleene star)
Definition 4.3.8 (N-fache Wiederholung). Die n-fache Konkatenation einer Sprache L mit sich selbst in der Potenznotation sei rekursiv definiert. Für n ≥ 1,n ∈ ℕ:
Hinweis
Formale Sprachen sind Mengen und somit können alle Mengenoperationen wie Schnitt (M ∩ N), Vereinigung (M ∪ N), Mengendifferenz (M ∖ N) mit ihnen verwendet werden.
Definition 4.3.12. Eine Sprache über Σ = {a1,a2,...,an} heisst regulär , wenn sie durch folgende reguläre Mengenausdrücke beschrieben werden kann:
Diese 6 Bildungsregeln reichen aus, um alle regulären Sprachen zu beschreiben. Meistens werden für die Kürze der Notation noch weitere Konstrukte definiert, welche sich aber immer auf obige 6 Bildungsregeln zurückführen lassen müssen.
Abschlusseigenschaften regulärer Sprachen
Definition 4.3.13. Eine Menge M heisst abgeschlossen (closed under) bezüglich einer Operation oder Funktion, wenn das Ergebnis der Operation mit Elementen aus M immer ein Element aus M ist.
Abschlusseigenschaften regulärer Sprachen
QUIZ Leichtes QUIZ zu Zeichenketten, Sprachen und Konkatenation
