2.2.1 Operationen auf Wörter und Sprachen
Definition: Länge eines Wortes & Häufigkeit eines Symbols im Wort
Die Länge eines Wortes \(w\) ist die Anzahl der Vorkommen aller Symbole. Wir notieren diese Länge mit \(|w|\).
Die Häufigkeit eines Symbols \(a\) im Wort \(w\) wird mit \(|w|_a\) bezeichnet.
Beispiele
-
- Für \(∑=\{a, b, c\}\) ist \(|a|=1, |aa|=|ab|=2, |abc|=3 \) und \(|ε|=0\).
- Für \(∑=\{0, 1\}\) ist \(|1101|=4 \).
- Für \(∑=\{01, 11\}\) ist \(|1101|=2 \).
- Für jedes Alphabet \(∑\) ist \(|ε|=0 \).
- Für \(∑_{Tast}\) ist \(|Das \: ist \: ein \: Satz.|=17 \), da Leerzeichen und Satzzeichen auch Symbole sind.
- Für \(∑=\{a, b, c\}\) ist \(|a|_a=1, |a|_b = 0, |aa|_a=2, |ab|_a=1, |abc|_c=1 \) und \(|abab|_c=0\).
- Für \(∑=\{0, 1\}\) ist \(|1101|_0=1 \) und \(|1101|_1=3 \).
- Für \(∑=\{01, 11\}\) ist \(|1101|_{01}=1 \).
- Für \(∑_{Tast}\) ist \(|Das \: ist \: ein \: Satz.|_s=2 \), da \(s\) und \(S\) zwei verschiedene Symbole sind.
Verkettung von Wörtern und Sprachen
Wir können Wörter aneinanderhängen, um neue Wörter zu generieren. Mit Wortpotenzen kann man Wörter kürzer darstellen. Mit den erlaubten Operationen für Sprachen lassen sich komplexe Sprachen einfacher darstellen. Schauen wir uns diese an.
Definition: Wortkonkatenation & Wortpotenzen
Seien \(x\) und \(y\) zwei beliebige Wörter. Dann steht \(x · y = xy\) für die Konkatenation (Verkettung) von \(x\) und \(y\).
Sei \(x\) ein Wort über einem Alphabet \(Σ\). Für alle \(i \in \mathbb{N}_{\geq 0}\) sind Wortpotenzen wie folgt definiert: \( x^0 = ε, x^1 = x \) und \(x^i = x·x^{i-1}\).
Beispiele
- Seien \(x = 01001\) und \(y = 110\) zwei Wörter, dann ist \(xy = 01001110\) die Konkatenation.
- Seien \(x\) ein beliebiges Wort, dann gilt \(xε=εx=x\).
- \(ababababbbbbbaaababa= (ab)^4b^5a^3(ba)^2\)
- \(abbabbaaabbaaabbaaabbaaa= (ab^2)^2a^3(b^2a^3)^3\)
Übung
- Sei \(xy\) die Konkatenation der Wörter \(x\) und \(y\), wobei \(|x|=4 \) und \(|y|=2 \). Wie lange ist dann das Wort \(xy\)? Antwort
- Verallgemeinern wir die letzte Frage. Sei \(xy\) die Konkatenation der Wörter \(x\) und \(y\), wobei \(|x|=n \) und \(|y|=m \). Wie lange ist dann das Wort \(xy\)? Antwort
Schauen Sie als Zusammenfassung der Formalen Sprachen bis zu diesem Punkt das folgende Video von Simpleclub:
Definition: Sprachkonkatenation & Kleensche Hülle von Sprachen
Sind \( A ⊂ Σ^∗\) und \(B ⊂ Γ^∗\) beliebige Sprachen, dann wird die Menge \(AB = \{uv | u ∈ A \) und \( v ∈ B\}\) als Konkatenation von \(A\) und \(B\) bezeichnet.
Die Kleenesche Hülle \( A^∗\) einer Sprache \( A\) ist durch \({ε} ∪ A ∪ AA ∪ AAA ∪ . . .\) definiert.
Bemerkung
Die Sprache \(AB\) besteht aus den Wörtern, die man ohne Überschneidung in ein Teilwort aus \(A\) und ein Teilwort aus \(B\) aufteilen kann.
Beispiele
- Die Sprache \(A\) enthält alle Binärwörter, die mit \(0\) enden. Die Sprache \(B\) enthält alle Binärwörter, die mit \(0\) beginnen.
\(00, 0000 \) und \(1100110011\) sind Wörter von der Sprache \(AB\).
\(ε\), \(0\) und \(01010\) sind keine Wörter von der Sprache \(AB\). Tipp - Für \(Σ= \{a, b\}, \: L_1 = \{a^i|i \geq 0\}= \{ε, a, aa, aaa, ….\}\) und \( L_2 = \{b^j|j \geq 0\}\) ist \( L_1L_2=\{a^ib^j|i\geq 0, j\geq 0\}=\{ε, a, b, aa, ab, bb, aaa, aab, abb, bbb, …\} = \) “alle Wörter über \(Σ\), in denen alle \(a\) vor allen \(b\) stehen”. Für diese Sprache macht es Sinn, sie als Konkatenation zu schreiben. (Dies ist dasselbe Beispiel wie im letzten Abschnitt, als es um die Notationen ging.)
- \(ε, 011011\) und \( 100101\) gehören zur Sprache \(\{00, 01, 10, 11\}^∗\), während \(111, 01010\) und \(0101110\) nicht dazugehören. Tipp
- Wie kann man die Elemente von \(\{00, 01, 10, 11\}^∗\) möglichst einfach beschreiben? Antwort
Übung
Hier haben Sie die Option Ihre Notizen zu diesem Abschnitt hochzuladen. Wir empfehlen eine sinnvolle Beschriftung z.B. 2_2_Operationen_FormaleSprache_Notizen.