Mit Google fortfahren
Formale Sprache: Alphabet, Wörter und Regeln
Eine formale Sprache ist eine genau festgelegte Menge endlicher Wörter über einem Alphabet. Du kannst deshalb mit eindeutigen Regeln prüfen, ob eine Zeichenfolge zur Sprache gehört. Die Syntax beschreibt dabei den Aufbau; eine Semantik kann den gültigen Zeichenfolgen zusätzlich Bedeutung geben.
Hake ab, was du schon kannst — und komm am Ende hierher zurück!
Vom Alphabet zur formalen Sprache
Stell dir einen Prüfer vor, der nur die Zeichen 0 und 1 akzeptiert. Diese erlaubten Zeichen bilden sein Alphabet.
Alphabet
Ein Alphabet $\Sigma$ ist eine endliche Menge erlaubter Symbole. Zum Beispiel gilt $\Sigma=\{0,1\}$.
Ein Wort über $\Sigma$ ist eine endliche Folge von Symbolen dieses Alphabets. 0, 101 und 1100 sind Wörter über $\{0,1\}$; 102 ist keines, weil 2 nicht zum Alphabet gehört.
$\Sigma^*$ bezeichnet die Menge aller endlichen Wörter über $\Sigma$, einschließlich des leeren Wortes. Eine formale Sprache wählt daraus bestimmte Wörter aus:
$$L\subseteq\Sigma^*$$
Über $\Sigma=\{0,1\}$ sei $L_0$ die Sprache aller nichtleeren Wörter, die auf 0 enden.
0gehört zu $L_0$.1010gehört zu $L_0$.1011gehört nicht zu $L_0$, weil das letzte Zeichen1ist.1020gehört nicht einmal zu $\Sigma^*$, weil es das unerlaubte Zeichen2enthält.
Beim Prüfen gehst du also in zwei Schritten vor: Zuerst kontrollierst du die verwendeten Symbole, danach die Sprachregel.
Alphabet → mögliche Wörter → Auswahl durch eine Regel. Erst diese Auswahl ist die formale Sprache.
Syntax und Semantik trennen
Ein Ausdruck kann korrekt aufgebaut sein, ohne in der gemeinten Situation sinnvoll zu sein. Dafür brauchst du zwei verschiedene Begriffe.
Syntax
Die Syntax umfasst die Regeln für den zulässigen Aufbau von Wörtern oder Ausdrücken. Eine Syntaxprüfung fragt: „Ist die Form erlaubt?“
Semantik
Die Semantik ordnet einem syntaktisch zulässigen Ausdruck eine Bedeutung zu. Sie fragt: „Was bedeutet der Ausdruck?“
Der Satz „Eine Blume kocht flüssige Uhren“ folgt einem möglichen deutschen Satzmuster, wirkt inhaltlich aber unsinnig. Das zeigt: Ein korrekter Aufbau garantiert noch keine sinnvolle Bedeutung.
Bei einer Programmiersprache prüft die Syntax beispielsweise, ob Zeichen und Bestandteile richtig angeordnet sind. Erst die Semantik legt fest, welches Verhalten eine gültige Anweisung bezeichnet.
Syntax prüft die Form. Semantik erklärt die Bedeutung.
Leeres Wort und leere Sprache unterscheiden
„Kein Zeichen“ und „kein Wort“ klingen ähnlich, sind mathematisch aber grundverschieden.
Leeres Wort
Das leere Wort $\varepsilon$ enthält null Symbole und hat die Länge $0$. Es ist trotzdem ein Wort.
Leere Sprache
Die leere Sprache $\varnothing$ enthält überhaupt kein Wort. Dagegen enthält $\{\varepsilon\}$ genau ein Wort, nämlich das leere Wort.
Daraus folgen drei verschiedene Fälle:
- $\varepsilon$: ein Wort ohne Zeichen
- $\{\varepsilon\}$: eine Sprache mit genau einem Wort
- $\varnothing$: eine Sprache ohne Wörter
Hängst du das leere Wort an abba, bleibt das Wort unverändert:
$$abba\varepsilon=\varepsilon abba=abba$$
Mit einer leeren Sprache kannst du dagegen kein Wort auswählen und daher auch kein Ergebniswort bilden.
Wähle in jeder Lücke die passende Form und prüfe anschließend deine Antworten.
Das Wort ohne Symbole heißt . Es wird mit bezeichnet. Die Menge $\{\varepsilon\}$ enthält , während $\varnothing$ enthält.
Wörter und Sprachen verketten
Bei der Konkatenation hängst du Zeichenfolgen ohne Zwischenraum aneinander. Die Reihenfolge ist entscheidend.
Für zwei Sprachen $L_1$ und $L_2$ enthält $L_1\circ L_2$ alle Wörter $uv$, bei denen $u$ aus $L_1$ und $v$ aus $L_2$ stammt:
$$L_1\circ L_2=\{uv\mid u\in L_1,\ v\in L_2\}$$
Gegeben sind $L_1=\{a,bb\}$ und $L_2=\{aa,b\}$. Jedes Wort aus $L_1$ wird mit jedem Wort aus $L_2$ verbunden:
aundaaergebenaaa.aundbergebenab.bbundaaergebenbbaa.bbundbergebenbbb.
Damit gilt:
$$L_1\circ L_2=\{aaa,ab,bbaa,bbb\}$$
Die zwei Auswahlmöglichkeiten aus $L_1$ und die zwei aus $L_2$ ergeben hier vier Paarungen.
Die Sprache $\{\varepsilon\}$ ist neutral, weil das leere Wort nichts hinzufügt:
$$L\circ\{\varepsilon\}=\{\varepsilon\}\circ L=L$$
Die leere Sprache ist dagegen absorbierend:
$$L\circ\varnothing=\varnothing\circ L=\varnothing$$
Konkatenation ist im Allgemeinen nicht vertauschbar. Aus a gefolgt von b wird ab; in umgekehrter Reihenfolge entsteht ba.
Potenzen und Kleene-Hülle verstehen
Sprachpotenzen beschreiben wiederholte Konkatenationen. Für jede Sprache gilt:
$$L^0=\{\varepsilon\}$$
Für $n\geq 0$ entsteht die nächste Potenz durch eine weitere Konkatenation mit $L$:
$$L^{n+1}=L^n\circ L$$
Für $L=\{a,b\}$ enthält $L^2$ alle Verkettungen aus zwei gewählten Wörtern:
$$L^2=\{aa,ab,ba,bb\}$$
Für die einelementige Sprache $K=\{ab\}$ gilt:
- $K^0=\{\varepsilon\}$
- $K^1=\{ab\}$
- $K^2=\{abab\}$
- $K^3=\{ababab\}$
Die Kleenesche Hülle $L^*$ vereinigt alle Potenzen ab der nullten:
$$L^*=\bigcup_{i\geq 0}L^i$$
Für $K=\{ab\}$ ist daher:
$$K^*=\{\varepsilon,ab,abab,ababab,\ldots\}$$
Der positive Abschluss $L^+$ beginnt dagegen mit $L^1$. Im Beispiel mit $K=\{ab\}$ enthält $K^+$ deshalb nicht $\varepsilon$.
$L^*$ enthält immer das leere Wort. Die Kleenesche Hülle muss aber nicht unendlich sein: Für $L=\varnothing$ gilt $L^*=\{\varepsilon\}$.
Eine formale Sprache selbst beschreiben
Eine kleine formale Sprache kannst du in drei Schritten festlegen:
- Bestimme das Alphabet.
- Formuliere eine eindeutige Bildungsregel.
- Prüfe gültige und ungültige Grenzfälle.
Gesucht ist eine Sprache für Codes aus genau drei Symbolen. Jeder Code beginnt mit A; danach folgen genau zwei Binärziffern.
Alphabet:
$$\Sigma=\{A,0,1\}$$
Bildungsregel: Das erste Symbol ist A. An zweiter und dritter Stelle steht jeweils 0 oder 1.
Sprache:
$$L_A=\{A00,A01,A10,A11\}$$
Grenzfälle:
A10ist gültig.A1ist zu kurz.AA0verwendet zwar nur Zeichen des Alphabets, verletzt aber die Stellenregel.B10enthält ein Zeichen außerhalb des Alphabets.
So trennt die Prüfung zwei mögliche Fehler: ein unerlaubtes Symbol und einen unerlaubten Aufbau.
Eine Sprache kann durch vollständige Aufzählung, eine mathematische Bedingung oder Regeln einer Grammatik beschrieben werden. Für die kleine Sprache $L_A$ ist die Aufzählung praktisch; bei einer unendlichen Sprache brauchst du eine endliche Regelbeschreibung.
Karteikasten
Überlege zuerst selbst und drehe die Karte anschließend zum Prüfen um.
Alles auf einen Blick
- Formale Sprache
- Alphabet: legt erlaubte Symbole fest
- Wort: reiht endlich viele Symbole aneinander
- Sprache: wählt Wörter aus $\Sigma^*$ aus
- Syntax: prüft den Aufbau
- Semantik: ordnet Bedeutung zu
- Konkatenation: verbindet Wörter in fester Reihenfolge
- Kleene-Hülle: sammelt beliebig viele Wiederholungen