Benutzer:Zahnradzacken/Symbole in der Theorie formaler Sprachen

Dieser Artikel ist im Entstehen und noch nicht Bestandteil der freien Enzyklopädie Wikipedia.

Solltest du über eine Suchmaschine darauf gestoVorlage:SSen sein, bedenke, dass der Text noch unvollständig sein und Fehler oder ungeprüfte Aussagen enthalten kann. Wenn du Fragen zum Thema hast, nimm Kontakt mit dem Autor Zahnradzacken auf.

Eine Mitarbeit am entstehenden Artikel ist ausdrücklich erwünscht.

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
$L\!\,$, ${\mathcal {L}}\!\,$	Sprache (engl. Language )	Die formale Sprache, die betrachtet wird.
$G\!\,$	Grammatik	Die formale Grammatik der betrachteten Sprache.
$\Sigma \!\,$	Alphabet	Die Menge der verwendbaren Zeichen.	$\Sigma _{1}$ = {0,1,2,3,4,5,6,7,8,9,+,-,*,/,.,=}   Alphabet für die Grundrechenarten
$A\!\,$			$\Sigma _{2}$ = {A,B,C,...,Y,Z,a,b,...,z,0,1,...,9,+,-,*,#,(,),[,],...}   umfangreicheres Alphabet
$T\!\,$	Terminal	Zeichen, aus denen die Wörter einer Sprache bestehen.
$a,b,c,d,n\!\,$	Zeichen	Symbole stehen für Zeichen aus dem vorhandenen Alphabet (Terminale).
$N\!\,$	Nichtterminal	Zeichen, die zur Erzeugung eines Wortes ersetzt werden müssen.	Begriffe wie <Verbalphrase>, <Satzzeichen>, <Operator> oder <Bezeichner>
$\langle$NichtTerminal$\rangle$	Backus-Naur-Darstellung für Nichtterminale
$V\!\,$	Vokabular, $V=N\cup T$	Das Vokabular der Grammatik.
$S\!\,$	Startsymbol	Das Nichtterminalsymbol, von dem aus die Erzeugung eines Wortes begonnen wird	$S$ kann für "Satz" stehen. Ersetzen durch $NP\;VP$ bedeutet, dass der Satz aus einer Nominal- und einer Verbalphrase besteht.
$P\!\,$	Produktionsregeln	Menge der Regeln, die gültige Ersetzungen von Nichtterminalen ermöglichen
Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle R\!\,}
Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \rho\!\,}
Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \alpha \rightarrow \beta\!\,}	Produktionsregel	Ein Vorkommen von Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \alpha} wird durch Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \beta} ersetzt.	Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle S \rightarrow NP\; VP}
Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \circ\!\,}	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	Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle ab \circ cd = abcd} (Konkatenation von Wörtern)
			Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \{a,b\} \circ \{c,d\} = \{ac,ad,bc,bd\}} (Konkatenation von Sprachen)
Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \vert\!\,}	Zusammenfassung mehrerer Regeln mit gleicher linken Seite in der Backus-Naur-Form		Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \alpha \rightarrow \beta_1 \vert\, \beta_2}
Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle w\!\,}	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.
Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \hat w\!\,}	Teilwort	Teilwort eines Wortes (Infix)
Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \varepsilon\!\,}	Leeres Wort	Ein Wort der Länge 0 (auch leerer String genannt)	Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle X\rightarrow \varepsilon} Anwendung dieser Regel löscht ein Vorkommen von Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle X}
Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \lambda\!\,}
Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \Sigma^*\!\,}	Kleenesche Hülle über dem Alphabet	Die Menge der durch Konkatenation bildbaren Wörter einschließlich des Leeren Wortes
Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle L^*\!\,}	Kleenesche Hülle über der Sprache

Grundbegriffe

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