Benutzer:Zahnradzacken/Symbole in der Theorie formaler Sprachen
Zur Darstellung formaler Spachen und derer Grammatiken werden typischerweise abstrakte Symbole verwandt. Diese Symbole sind zwar nicht vereinheitlicht; für ihren Gebrauch haben sich aber grundlegende Konventionen durchgesetzt, die normalerweise nicht jedesmal eigens erklärt werden. Die folgende Tabelle ist daher lediglich dazu gedacht, eine Übersicht über gebräuchliche Symbole und ihre Benutzung zu geben – sie ist jedoch weder vollständig, noch in irgendeiner Form verbindlich, da es letztlich vom jeweiligen (Computer-)Linguisten bzw. (Theoretischen) Informatiker abhängt, welche Darstellungsform er wählt.
Da formale Grammatiken zu großen Teilen mit Symbolen der Mengenlehre ausgedrückt werden, sei an dieser Stelle auch auf die Liste der Symbole in der Mengenlehre und die Tabelle logischer Symbole verwiesen.
Symbol(e) | Bezeichnung | Erklärung | Beispiele |
---|---|---|---|
, | Sprache (engl. Language) | Die formale Sprache, die betrachtet wird. | |
Grammatik | Die formale Grammatik der betrachteten Sprache. | ||
Alphabet | Die Menge der verwendbaren Zeichen. | = {0,1,2,3,4,5,6,7,8,9,+,-,*,/,.,=} Alphabet für die Grundrechenarten | |
= {A,B,C,...,Y,Z,a,b,...,z,0,1,...,9,+,-,*,#,(,),[,],...} umfangreicheres Alphabet | |||
Terminal | Zeichen, aus denen die Wörter einer Sprache bestehen. | ||
Zeichen | Symbole stehen für Zeichen aus dem vorhandenen Alphabet (Terminale). | ||
Nichtterminal | Zeichen, die zur Erzeugung eines Wortes ersetzt werden müssen. | Begriffe wie <Verbalphrase>, <Satzzeichen>, <Operator> oder <Bezeichner> | |
NichtTerminal | Backus-Naur-Darstellung für Nichtterminale | ||
Vokabular, | Das Vokabular der Grammatik. | ||
Startsymbol | Das Nichtterminalsymbol, von dem aus die Erzeugung eines Wortes begonnen wird | kann für "Satz" stehen. Ersetzen durch bedeutet, dass der Satz aus einer Nominal- und einer Verbalphrase besteht. | |
Produktionsregeln | Menge der Regeln, die gültige Ersetzungen von Nichtterminalen ermöglichen | ||
Produktionsregel | Ein Vorkommen von wird durch ersetzt. | ||
Konkatenationsoperator für Wörter und formale Sprachen. | Durch Konkatenation können einzelne Wörter oder alle Wörter zweier Sprachen aneinander gehängt werden | (Konkatenation von Wörtern) | |
(Konkatenation von Sprachen) | |||
Zusammenfassung mehrerer Regeln mit gleicher linken Seite in der Backus-Naur-Form | |||
Wort | Mit dem vorhandenen Alphabet gebildetes Wort. | Ein <Bezeichner> oder ein <Reserviertes Wort>, wie 'if', 'defun', 'return', ein Leeres Wort oder auch sinnfreie Wörter. | |
Teilwort | Teilwort eines Wortes (Infix) | ||
Leeres Wort | Ein Wort der Länge 0 (auch leerer String genannt) | Anwendung dieser Regel löscht ein Vorkommen von | |
Kleenesche Hülle über dem Alphabet | Die Menge der durch Konkatenation bildbaren Wörter einschließlich des Leeren Wortes | ||
Kleenesche Hülle über der Sprache |
Grundbegriffe
[Bearbeiten | Quelltext bearbeiten]Ein Zeichen ist ein Zeichen ist ein Zeichen !!=== Zeichen ===