Zurück zum Index

Autoren-Aufruf! Ich habe seit Jahren keine Zeit und Lust mehr, die Inhalte von Mandalex zu pflegen, weswegen sie teilweise veraltet und inkorrekt sind. Wenn ein Wikipedia-Autor über diese Seite stolpert und Lust hat, meine Texte irgendwie in Wikipedia zu integrieren, darf er oder sie mir eine Email schreiben, ich würde die einzelnen Seiten dann gerne abgeben, auf dass ich die Seite irgendwann schliessen kann. Und bevor die Frage kommt: Nein, ich zahle nichts.

Grammatik:

G(V,A,P,S)	Grammatik
V	Variablen, nicht-terminal-Symbole, grammatikalische Typen
A	Alphabet, terminal-Symbole
S	Startsymbol, ein Element aus V
P	Produktionen der Form L -> R, wobei L und R eine Zusammensetzung von Faktoren sind
(V OR A)	Faktor
w	Wort, besteht nur aus Terminalsymbolen = A*

Beispiel:
V = Satz, doppelnull, nulleins
A = '0', '1'
S = Satz
P = Satz -> doppelnull ( nulleins* | 11 )
doppelnull -> 00
nulleins -> 01

Dadurch können folgende Wörter w erstellt werden:
00, 0001, 000101, 00010101, 0001010101, ... und 0011

regular Expressions:

Eine Sprache kann auch definiert werden durch eine regular Expression:
* steht für beliebig viele Wiederholungen, also 0 mal, 1 mal, ... unendlich viel mal.
| steht für das ODER: entweder der Faktor, der links des Strichs steht, oder der rechts.
Die durch | abgegrenzten Teile werden Terme genannt. Achtung: | bindet weniger stark wie Faktoren. Beispiel:
S -> 0 1 | 0 ergibt nicht die Wörter 01 und 00, sondern 01 und 0.
Es sind aber auch Klammerungen möglich: S -> 0 ( 1 | 0 ) ergibt nun also 01 und 00.

Sprache:

L(G)	Sprache
L(G)	{ w Element von A* | S ->* w } anders gesagt die Menge aller Wörter, die beginnend mit dem Startsymbol konstruiert werden können.

Typen von Sprachen:

Zur Erinnerung: Die Buchstaben L und R stellen den linken und rechten Teil einer Produktion dar: L -> R
Typ 0: alles ist erlaubt: phrase structure grammar
Typ 1: Menge von L ist kleinergleich Menge von R: context sensitive.
Typ 2: Jedes L ist ein Element von V: context free.
Typ 3: L ist Element von V, und R ist entweder ein Terminalsymbol oder ein Terminalsymbol, gefolgt von einer Variable. regular. Parser arbeiten mit regulären Sprachen effizienter.