Formale Sprache: Alphabet, Wörter und Regeln
Du lernst, wie du Wörter aus erlaubten Zeichen bildest, ihre Regeln und Bedeutung unterscheidest und Wörter aneinanderhängst.
Kurz gesagt
Eine formale Sprache ist eine festgelegte Sammlung von Wörtern über einem Alphabet, also einer Sammlung erlaubter Zeichen oder Zeichengruppen. Ein Wort gehört dazu, wenn es daraus besteht und die Bedingung der Sprache erfüllt.
Aus wenigen Zeichen kannst du viele Folgen bilden. Du legst dabei genau fest, welche Zeichen erlaubt sind und welche Folgen dazugehören. Die Alphabete, Regeln und Bedeutungen in unseren Beispielen sind ausgedacht.
Deine Lernziele
Ein Alphabet ist eine festgelegte Sammlung von Symbolen. Ein Symbol ist eine Einheit, die du als Ganzes verwendest. Das Alphabet enthält mindestens ein Symbol und nur endlich viele: Du kannst seine Symbole vollständig aufzählen. Wir schreiben sie in einer festen Reihenfolge auf. Wörter müssen diese Reihenfolge nicht einhalten.
Ein Symbol kann ein einzelnes Schriftzeichen sein. Es kann aber auch aus mehreren Schriftzeichen bestehen. Wenn ein Alphabet „auf“ als ein Symbol festlegt, zählt diese ganze Einheit als ein Symbol.
Ein Wort über einem Alphabet ist eine endliche Folge seiner Symbole. Endlich bedeutet: Die Folge hat eine bestimmte Anzahl von Symbolen und endet. Diese Anzahl heißt Länge des Wortes. Symbole dürfen sich wiederholen. Ihre Reihenfolge zählt: „rs“ und „sr“ sind verschiedene Wörter. Auch eine Folge mit null Symbolen ist ein Wort; sie heißt leeres Wort.
Eine formale Sprache ist eine ausgewählte Sammlung von Wörtern über einem Alphabet. Du kannst die Auswahl durch eine Bedingung festlegen oder alle enthaltenen Wörter aufzählen. Jedes Wort der Sprache besteht aus Symbolen des Alphabets. Trotzdem muss nicht jedes mögliche Wort zur ausgewählten Sprache gehören.
Formale Sprache
Eine formale Sprache enthält ausgewählte Wörter über einem festgelegten Alphabet. Welche Wörter dazugehören, ist genau bestimmt.
Beispiel: Alphabet, Wort und Sprache auseinanderhalten
- 1Unser Alphabet enthält genau die Symbole „r“ und „s“.
- 2„srr“ ist ein Wort über diesem Alphabet. Es hat drei Symbole.
- 3Unsere Sprache enthält genau die Wörter mit einem Symbol: „r“ und „s“.
- 4„srr“ ist ein Wort über dem Alphabet, gehört aber nicht zu dieser Sprache.
Teste dich
Prüfe zuerst die Symbole: Stammt jedes Symbol der Folge aus dem festgelegten Alphabet? Ein fremdes Symbol reicht aus, damit die Folge kein Wort über diesem Alphabet ist. Beachte dabei, was als ein Symbol festgelegt wurde. Eine Einheit aus mehreren Schriftzeichen zählt als Ganzes.
Prüfe danach die Bedingung der Sprache. Sie kann zum Beispiel eine bestimmte Länge oder ein bestimmtes letztes Symbol verlangen. Lies die ganze Bedingung. Wenn sie mehrere Anforderungen enthält, müssen alle erfüllt sein.
Eine Folge gehört genau dann zur Sprache, wenn beide Prüfungen passen: Alle Symbole stammen aus dem Alphabet und die Bedingung ist erfüllt. Erlaubte Symbole allein reichen nicht aus.
Beispiel: Zwei Prüfungen für eine Sprache
- 1Das Alphabet enthält genau „k“ und „l“.
- 2Zur Sprache gehören genau die Wörter mit zwei Symbolen, die mit „l“ enden.
- 3„kl“ gehört dazu: Beide Symbole sind erlaubt, es hat zwei Symbole und endet mit „l“.
- 4„kk“ gehört nicht dazu: Die Symbole sind erlaubt, aber das letzte Symbol ist „k“.
- 5„xl“ gehört nicht dazu: „x“ stammt nicht aus dem Alphabet.
Merke: Prüfe erst die erlaubten Symbole und dann die ganze Sprachbedingung. Beides muss stimmen.
Teste dich
Die Syntax legt die Regeln für den erlaubten Aufbau von Zeichenfolgen fest. Dazu können ihre Länge oder die Reihenfolge ihrer Symbole gehören. Mit diesen Regeln prüfst du, ob eine Zeichenfolge zur formalen Sprache gehört.
Die Semantik gibt Zeichenfolgen eine Bedeutung. Diese Bedeutung wird zusätzlich festgelegt. Aus der erlaubten Anordnung der Symbole allein ergibt sie sich nicht.
Eine Zeichenfolge kann nach den Regeln erlaubt sein, obwohl ihr noch keine Bedeutung zugeteilt wurde. Du kannst also den Aufbau prüfen, ohne eine Bedeutung zu kennen. Wenn du eine vereinbarte Bedeutung änderst, bleiben die erlaubten Wörter gleich, solange du die Regeln für ihren Aufbau beibehältst.
Beispiel: Eine erfundene Zeichensprache
- 1Das Alphabet enthält genau „f“ und „g“.
- 2Die Syntax verlangt genau zwei Symbole und am Anfang „f“. Damit sind genau „ff“ und „fg“ erlaubt.
- 3Für „fg“ vereinbaren wir die Bedeutung „Nimm einen Stift.“ Das ist eine Festlegung der Semantik.
- 4Für „ff“ vereinbaren wir keine Bedeutung. Es ist trotzdem nach der Syntax erlaubt.
Merke: Syntax betrifft den erlaubten Aufbau. Semantik betrifft die zusätzlich zugeordnete Bedeutung.
Teste dich
Das leere Wort besteht aus null Symbolen. Sein Zeichen ist \varepsilon, gesprochen „Epsilon“. Dieses Zeichen bezeichnet das leere Wort; es ist kein zusätzliches Symbol im Wort. Ein Leerzeichen ist dagegen ein Symbol, wenn es zum Alphabet gehört.
Die leere Sprache enthält kein einziges Wort. Ihr Zeichen ist \varnothing, gesprochen „leere Menge“. Sie enthält auch das leere Wort nicht. Eine Sprache, die das leere Wort und sonst nichts enthält, hat dagegen genau ein Wort. Verwechsle also die Anzahl der Wörter einer Sprache nicht mit der Anzahl der Symbole eines Wortes.
Konkatenation bedeutet Verkettung. Du hängst das zweite Wort direkt hinter das erste. Dabei bleiben alle Symbole in ihrer Reihenfolge erhalten. Es kommt kein Trennzeichen hinzu, und gleiche Symbole an der Grenze verschmelzen nicht. Die Reihenfolge der Wörter ist wichtig. Wenn du das leere Wort vor oder hinter ein Wort hängst, bleibt dieses Wort unverändert.
Die kleenesche Hülle eines Alphabets enthält alle endlichen Wörter über diesem Alphabet. Wenn das Alphabet den Namen A hat, schreiben wir für seine Hülle A^*, gesprochen „A Stern“. Dazu gehört auch das leere Wort. Du darfst die Symbole beliebig oft wiederholen und beliebig anordnen. Jedes einzelne Wort bleibt endlich, aber es gibt keine größte erlaubte Wortlänge. Eine Sprache über diesem Alphabet wählt Wörter aus dieser Hülle aus. Sie kann kein Wort, endlich viele Wörter oder unendlich viele Wörter enthalten.
| Begriff | Was ist enthalten? |
|---|---|
| Leeres Wort | Null Symbole |
| Leere Sprache | Kein Wort |
| Sprache nur mit dem leeren Wort | Genau ein Wort mit null Symbolen |
Beispiel: Wörter bilden und verketten
- 1Das Alphabet mit dem Namen A enthält genau „m“ und „n“.
- 2Seine kleenesche Hülle enthält zum Beispiel das leere Wort, „m“, „n“, „mm“, „mn“, „nm“ und „nn“.
- 3Verkette „mn“ mit „n“: Hänge das zweite Wort hinten an. Es entsteht „mnn“.
- 4Auch „mnn“ gehört zur Hülle. Die beiden benachbarten „n“ bleiben erhalten.
- 5Verkettest du „mn“ mit dem leeren Wort, bleibt „mn“ unverändert.
Teste dich
Alles auf einen Blick
Formale Sprache
Es legt endlich viele erlaubte Symbole fest und enthält mindestens eines.
Ein Wort ist eine endliche Symbolfolge. Eine formale Sprache ist eine festgelegte Auswahl solcher Wörter.
Alle Symbole müssen erlaubt sein und die ganze Sprachbedingung muss passen.
Syntax regelt den Aufbau. Semantik gibt Zeichenfolgen zusätzlich eine Bedeutung.
Das leere Wort hat null Symbole. Die leere Sprache enthält kein Wort.
Verkettung hängt Wörter aneinander. Die kleenesche Hülle enthält alle endlichen Wörter des Alphabets, auch das leere Wort.
Das Wort „eete“ auf Zugehörigkeit prüfen
- 1Aufgabe: Das Alphabet enthält genau „e“ und „t“. Zur Sprache gehören genau die Wörter, in denen „t“ genau einmal vorkommt. Prüfe „eete“.
- 2Zerlege das Wort in seine Symbole: „e“, „e“, „t“, „e“.
- 3Prüfe das Alphabet: Jedes dieser Symbole ist erlaubt.
- 4Prüfe die Bedingung: „t“ kommt genau einmal vor.
- 5Ergebnis: „eete“ gehört zur Sprache, weil beide Prüfungen passen.
Fehler finden
Fehler in Zeile 3Erlaubte Symbole allein reichen nicht aus. Richtig: „vuu“ gehört nicht zur Sprache, weil es drei statt zwei Symbole hat.
Lückentext
Das Alphabet enthält genau „g“ und „h“. Das Wort „ghhg“ hat Symbole. Die Vereinbarung, dass „xy“ „Bleib stehen.“ bedeutet, gehört zur . Zum Alphabet gehören genau „p“ und „q“. Seine kleenesche Hülle enthält , denn jedes Symbol eines enthaltenen Wortes muss aus diesem Alphabet stammen.