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 gestoßen 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
$R\!\,$
$\rho \!\,$
$\alpha \rightarrow \beta \!\,$	Produktionsregel	Ein Vorkommen von $\alpha$ wird durch $\beta$ ersetzt.	$S\rightarrow NP\;VP$
$\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	$ab\circ cd=abcd$ (Konkatenation von Wörtern)
			$\{a,b\}\circ \{c,d\}=\{ac,ad,bc,bd\}$ (Konkatenation von Sprachen)
$\vert \!\,$	Zusammenfassung mehrerer Regeln mit gleicher linken Seite in der Backus-Naur-Form		$\alpha \rightarrow \beta _{1}\vert \,\beta _{2}$
$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.
${\hat {w}}\!\,$	Teilwort	Teilwort eines Wortes (Infix)
$\varepsilon \!\,$	Leeres Wort	Ein Wort der Länge 0 (auch leerer String genannt)	$X\rightarrow \varepsilon$ Anwendung dieser Regel löscht ein Vorkommen von $X$
$\lambda \!\,$
$\Sigma ^{*}\!\,$	Kleenesche Hülle über dem Alphabet	Die Menge der durch Konkatenation bildbaren Wörter einschließlich des Leeren Wortes
$L^{*}\!\,$	Kleenesche Hülle über der Sprache

Grundbegriffe

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