Zur Themenübersicht

reguläre Sprachen, ursprüngliche Definition

Der Begriff regulärer Ausdruck wurde ursprünglich folgendermaßen definiert:

Sei A ein Alphabet. Ein regulärer Ausdruck ist eine Zeichenfolge, die aus Elementen von A und einigen weiteren Zeichen (Klammern, È, *, ε) nach folgenden Regeln rekursiv gebildet wird.

Jedes Zeichen a Î A ist ein regulärer Ausdruck.
Ein spezielles Zeichen ε für das leere Wort ist ein regulärer Ausdruck.
Sind R, S reguläre Ausdrücke, so auch R S, die einfache Aneinanderreihung der Ausdrücke.
Sind R, S reguläre Ausdrücke, so auch R È S, die Alternative R oder S.
Ist R ein regulärer Ausdruck, so auch R *. "*" bedeutet n-malige Wiederholung, n ≥ 0 beliebig.
Genau die durch die Schritte 1. bis 5. konstruierbaren Ausdrücke sind regulär.

Der *-Operator hat hierbei höhere Priorität als die Aneinanderreihung und die Alternative.
Reihung hat höhere Priorität als Alternative. Überflüssige Klammern werden häufig weggelassen.

Ohne Beweis folgende Aussage:
Die hiermit definierte Menge von regulären Sprachen ist äquivalent zur Menge der Sprachen, die von rechtslinearen (bzw. linkslinearen) Grammatiken erzeugt werden.

Beispiele:

Sei A={a,b}

ab* bezeichnet die Menge aller Worte, die mit a beginnen und mit einer beliebigen Anzahl von b’s enden

a*bba* ist die Menge aller Worte, die genau zwei b’s enthalten.

(aÈb)* enthält alle Zeichenketten, die aus a oder b gebildet werden können.

(aÈab)* ist die Menge aller Worte aus a’s und b’s, die mit einem a beginnen und keine zwei aufeinanderfolgenden b’s enthalten, während (bÈe)(aÈab)* auch mit einem b beginnen darf (e ist wie immer das leere Wort).

Zur Themenübersicht
Zum Seitenanfang
Zur vorigen Seite	Zur nächsten Seite

Hannah-Arendt-Gymnasium, Lengerich