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.