Sprachen | Worte | Alphabete

anchored to 112.00_anchor_overview

Motivation

Wir möchten hier Alphabete und Worte definieren, weil wir grundsätzlich gerne ein formales Modell eines Computers erzeugen möchten –> siehe 112.02_deterministische_automaten Um dies tun zu können, müssen wir eine formale Struktur schaffen, um eine Sprache beschreiben zu können, mit welcher dann die Aufgaben ( also das was der Automat verarbeiten soll/muss) beschrieben werden können.

Alphabete | Worte

Wir beginnen folgend mit den Definitionen eines Alphabets und daraus konstruierbaren Worten:

Alphabete

[!Definition] $\sigma$ Alphabete Ein Alphabet ist eine endliche Menge $\Sigma$ von Zeichen (symbolisch gedacht und eher abstrakt bedacht, kann also beliebig sein!) Die Elemente von $\Sigma$ heißen dabei dann die Symbole/Buchstaben –> müssen aber keine default Buchstaben sein!

Daraus kann man jetzt Verkettungen basteln, die dann einem Wort entsprechend:

Wörter

[!Tip] Wörter $w=w_1{w}_2\dots w_n$
Wir definieren ein Wort $w$ über einem Alphabet $\Sigma$ was eine endliche Folge von beliebigen Zeichen aus dem Alphabet $\Sigma$ ist. Die Länge eines Wortes $w$ ist dabei die Anzahl der Zeichen in W, beschrieben mit $\mid w\mid$ Wir beschreiben es dann mit $w=w_1,w_2,\dots ,w_n$ was dann entsprechend Zeichen beschreibt mit den einzelnen Bestandteilen. $\in \Sigma$

Ein Wort können wir uns oft als Liste vorstellen, also eine Reihung/Sortierung der Buchstaben/Zeichen, die es hat!

Natürlich können wir Wörter auch konkatenieren. Beschrieben mit: $$w_1{w}_2=w_{\text{neu}}$$

leeres Wort

[!Information] Leeres Wort Weiterhin brauchen wir ein Leeres Wort Dieses brauchen wir vor Allem dann, wenn wir ein System haben, bei welchem auch eine leere Eingabe nicht zum “Absturz” führen soll, also wir es so definieren, dass man mit diesem auch eine leere Sprache bzw. leere Wörter verarbeiten kann.

Beschrieben wird es mit $ϵ$ Das leere Wort hat eine Länge von $0$

[!Warning] $\ne \varnothing$ es ist nicht equivalent zur leeren Menge, sondern ist eine leere Folge von Zeichen!

Beispiele

Ferner ein paar simple Beispiele zur Illustration: $\Sigma =\{0,1\}$ beschreibt etwas das Alphabet, was binäre Zahlen darstellen kann.

Es ermöglicht die Bildung von Ketten von 0,1: $w_1=000011101010$ $w_2=001100,|w\mid =6$

$\Sigma =\{a,b,c,\dots ,z\}$ wäre ein Alphabet für kleine lateinische Buchstaben

$w_1=tschaa$ $w_2=sowas,\mid w\mid =5$

Teilworte

Wir haben soeben bereits gezeigt, wie man ein Wort aus verschiedenen Ketten von Symbolen beschreiben kann. Weiterhin haben wir noch betrachtet, wie man Wörter miteinander konkatenieren kann - um so etwa neue bilden zu können.

[!Definition] Teilwort Wir nennen ein Wort $x$ ein Teilwort eines anderen Wortes $y$, wenn wir $y$ umschreiben können, sodass: $$y=u\cdot x\cdot v\mid u,v\in {\Sigma }^{\ast }$$ Also wir können etwas davor und dahinter anbringen, damit dann $x$ zu $y$ ergänzt werden kann!

[!Tip] Präfixe Wenn hier jetzt $u=ϵ$, dann nennen wir $x$ das Präfix von $y$ (denn es ist der Anfang vom Wort ( und danach kommt ein Filler $v$))

[!Tip] Suffixe Wenn in der Betrachtung jetzt $v=ϵ$, dann ist $x$ das Suffix von $y$. Auch hier, weil wir mit $x$ das Ende von $y$ beschreiben und davor irgendein Filler $u$ das Wort füllt.

Beispiele dafür:

• $01$ bildet ein Teilwort von $00111$
• $10$ kann ein Präfix von $10100$ oder $1000101010$ sein
• $011$ ist ein Suffix von $00011$ oder $01011010101011$
• $ϵ$ ist ein Suffix und Präfix eines jeden Wortes - auch von sich selbst!

Sprachen

Wir haben nun das Werkzeug, um Alphabete und Worte zu generieren und beschreiben. Daraus können jetzt Mengen geschaffen werden, die dann ferner betrachtet eine Sprache bilden können ( wir können dann auch noch Automaten finden, die diese Sprachen beschreiben können ( für manche zumindest!) 112.02_deterministische_automaten)

Alphabeten-Mengen

Grundsätzlich möchten wir für Sprachen Mengen beschreiben, die eine gewisse Länge von Zeichen erlaubt / angibt .

[!Definition] Menge aller Wörter der Länge $n$ Möchten wir die Menge aller Wörter einer bestimmten Länge $n$ definieren / charakterisieren, dann benötigt es ein bestimmtes Alphabet für das es gilt. Ferner beschreiben wir dann für Wörter der Länge $n$ mit $${\Sigma }^n$$ alle Wörter die Symbole aus dem Alphabet in Länge $n$ beschreiben kann.

[!Important] ${\Sigma }^0=\{ϵ\}$
Als Sonderfall beschreibt diese Menge nicht das leere Wort oder die leere Menge, sondern die Menge, die nur das leere Wort enthält!

Kleen’sche Hülle ${\Sigma }^{\ast }$

Neben der Mengen für Wörter der Länge $n$ in Abhängigkeit eines Alphabets $\Sigma$ gibt es ferner noch eine allumfassende Menge:

[!Definition] Kleen’sche Hülle ${\Sigma }^{\ast }$ Mit der Kleen’schen Hülle für ein Alphabet $\Sigma$ beschreiben wir die Menge aller Wörter, die man mit $\Sigma$ beschreiben kann. ( Also alle Wörter mit beliebiger Länge etc!, die man mit den Symbolen bilden kann) $$\Sigma =\bigcup _{n=0}^{\infty }{\Sigma }^n$$

( Diese Menge schließt auch die leeren Wörter ein!)

[!Tip] Menge aller nicht leeren Worte: ${\Sigma }^{+}={\bigcup }_{n=1}^{\infty }{\Sigma }^n$ Hier werden also nur nicht leere Wörter beschrieben, weil ${\Sigma }^0$ rausfällt!

Sprache

Da wir mit dieser Menge einfach alles, was man mit einem Alphabet bilden könnte, abdecken, können wir Sprachen hinein-strukturieren.>

[!Definition] Sprache $L$ Wir beschreiben mit $L$ für ein Alphabet $\Sigma$ eine Sprache, was eine Menge von Wörtern über $\Sigma$ ist. Formal gilt hier $$L\subseteq {\Sigma }^{\ast }$$

Beispiele

Wir können bestimmte Sprachen abhängig von ihrem Alphabet beschreiben

Dabei müssen wir nicht immer genau angeben, wie das möglich ist, sondern können durch Text vereinfachen!

$\Sigma =\{a,b\}={\Sigma }^2=\{aa,ab,ba,bb\}$ $\Sigma =\{a,b,c,d,\dots z,A,B,C,\dots \}=L=\{w\in \text{ Duden}\}$ -> damit lassen sich alle deutschen Wörter definieren / beschreiben! ( natürlich auch viel Müll dazwischen, aber das ist nicht relevant, daher haben wir die Einschränken, dass es im Duden ist!) $\Sigma =\{0,1\},L=\{w\in {\Sigma }^{\ast }\mid w\text{ ist gerade Bina¨rzahl}\}$ $\Sigma =\{0,1\},L=\{w\in {\Sigma }^{\ast }\mid w\text{ ist durch 3 teilbar }\}$

[!Important] Alphabet endlich, Sprache vielleicht nicht! $\Sigma =\{a,b\},L=\{ab,abab,ababab,\dots \}$ Hier sehen wir, dass die Sprache unendlich viele Wörter beinhalten kann, dabei aber ein endliches Alphabet haben

Weiter Folgerungen hieraus:

[!Important] Sprachen können unendlich viele Wörter haben

[!Tip] Es gibt unendlich viele Sprachen über ein Alphabet $\Sigma$ ( auch wenn es endlich ist!)

Operationen auf Sprachen

Wir können ferner, wie bei anderen Mengen, diverse Operationen auf Sprachen ausführen / anwenden!

Vereinigung $L_1\cup L_2=\{w\in {\Sigma }^{\ast }\mid w\in L_1\vee w\in L_2\}$

Durchschnitt $L_1\cap L_2=\{w\in {\Sigma }^{\ast }\mid w\in L_1\wedge w\in L_2\}$

Differenz $L_1\setminus L_2=\{w\in {\Sigma }^{\ast }\mid w\in L_1\wedge w\notin L_2\}$

Komplement $\overline{L}=\{w\in {\Sigma }^{\ast }\mid w\notin L\}$

Konkatenation $L_1\cdot L_2=\{w_1{w}_2\mid w_1\in L_1,w_2\in L_2\}$

[!Important] Kleen’sche Hülle $L^{\ast }={\bigcup }_{k=0}^{\infty }{L}^k=\{x_1\dots x_{k|}\mid x_i\in L\forall i\le k,k\in \mathbb{N}\}$ Diese Hülle ist insofern interessant, dass sie $\subseteq {\Sigma }^{\ast }$ ist ( was alle Sprachen sind xd) aber vor Allem eine Konkatenation von den Wörtern, die sich in dieser Sprache befinden!

[!Important] Positive Hülle (einer Sprache) $L^{+=}{\bigcup }_{k=0}^{\infty }{L}^k$ ähnlich der kleen’schen Hülle, nur ohne leeres Wort, da $L^0$ nicht gezählt wird

Further links

Sprachen bilden das fundamentale Konzept, was wir in weiteren Themen brauchen, um Automaten zu bezeichnen, ihre Limits zu finden etc. Siehe etwa:

• 112.02_deterministische_automaten
• 112.04_non_deterministische_automaten etc