Alphabet, Wort, Sprache (BP Items 1,2,3,15)³

Die Verarbeitung von Eingaben setzt immer eine festgelegte Menge erlaubter Zeichen voraus. Diese Menge nennt man Alphabet, typischerweise mit dem Buchstaben Σ (groß Sigma) bezeichnet. Kombinationen dieser Alphabetzeichen heißen Wörter; auch das leere Wort ∅ (das kein Zeichen enthält) ist möglich.

Eine Menge von Wörtern heißt Sprache. Eine Sprache kann durch Formel- oder Verbalbeschreibung, oft auch durch vollständige Aufzählung ihrer Wörter festgelegt werden:

Es gibt aber weitaus mächtigere und flexiblere Arten, Sprachen zu beschreiben: Im Folgenden werden dazu insbesondere reguläre Ausdrücke, Syntaxdiagramme und verschiedene Arten von Grammatiken behandelt.

Die Fachwort „Wort“ ist leider didaktisch schwierig, denn anders als in der Alltagssprache bezeichnet es die gesamte Eingabe (in den formalen Sprachen gibt es also keine „Sätze“). Treten in der Eingabe Leerzeichen auf, wie etwa in einem Java-Programm, sprechen Schüler gern von einzelnen „Wörtern“ innerhalb des Programms – tatsächlich besteht das Wort aber aus der gesamten Datei.

Auch das leere Wort ε (das kein Zeichen enthält) wird leicht mit der leeren Sprache (die keine Wörter enthält) verwechselt. Die Unterscheidung ist aber wichtig, denn während die leere Sprache tatsächlich so langweilig ist, wie sie klingt, hat das leere Wort durchaus praktische Relevanz: Für die Sprache der „korrekt geklammerten Ausdrücke“, in denen wie in (()()) alle geöffneten Klammern korrekt wieder geschlossen werden, stellt sich die Frage, ob denn gar keine Klammern auch zulässig wären? In der Regel wird das leere Wort durchaus als „korrekt geklammert“ angesehen; dagegen gibt es keine leere, gültige Mailadresse.

Die oben erwähnte Gültigkeitsprüfung heißt in der Fachsprache Wortproblem: Gehört ein bestimmtes Wort zu einer gegebenen Sprache? Zur Lösung dieses Problems setzt man in der Praxis verschiedene Typen von Automaten ein, die in Software implementiert werden können; die Schüler lernen aber auch, Wortprobleme mit anderen Beschreibungsmitteln (Syntax­dia­grammen und Grammatiken) auf Papier zu lösen.

In der Theorie der formalen Sprachen geht es ausschließlich um die Syntax von Sprachen, also um deren Aufbau und Struktur: In einer E-Mailadresse muss das @ beispielsweise genau ein Mal vorkommen, darf nicht als erstes Zeichen stehen, und danach muss ein gültiger Domain­name folgen.

Die Semantik dieser Sprachen, also die Bedeutung der einzelnen Bestandteile, wird nicht betrachtet, auch wenn sie für die tatsächliche Weiterverarbeitung eines Input natürlich essenziell ist. Eine nach den Regeln korrekt angegebene Mailadresse kann beispielsweise existieren oder auch nicht; ein Java-Programm wird nach der Übersetzung von der virtuellen Maschine aus­ge­führt und soll dann genau das tun, was das Java-Programm beschreibt. Beide Fragen betreffen die Bedeutung, also die Semantik.

Erst recht ignoriert die Theorie die Pragmatik (also die nicht-wörtliche Interpretation mit Hilfe von Welt- und Kontextwissen), die in der Alltagssprache so wichtig ist: Erst die Prag­ma­tik gibt dem Dialog „Hast du eine Jacke mit?“ – „Ach, heute ist bestimmt gutes Wetter!“ einen Sinn.

Die meisten Automaten verarbeiten eine Eingabe (ein Wort) zeichenweise und können auf jedes „verbrauchte“ Zeichen mit einer Zustandsänderung, manche Typen von Automaten auch mit weiteren Aktionen reagieren.

³ Die meisten Überschriften nennen relevante Items des Bildungsplans (innerhalb Abschnitt 3.3.5 des BP).

Hintergrundinformationen: Herunterladen [odt][669 KB]

Weiter zu Mealy-Automaten