Benutzer:Zahnradzacken/Symbole in der Theorie formaler Sprachen

aus Wikipedia, der freien Enzyklopädie
Zur Navigation springen Zur Suche springen

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.

 

Gebräuchliche Symbole formaler Grammatiken
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    


Ein Zeichen ist ein Zeichen ist ein Zeichen !!=== Zeichen ===

Produktionsformen

[Bearbeiten | Quelltext bearbeiten]