Grundlagen

Alphabet, Wort, Sprache

Definition: Ein Alphabet ist eine endliche, nichtleere Menge von Zeichen (Symbolen). Ein geordnetes Alphabet ist ein Alphabet, dessen Zeichen gemäß einer Ordungsrelation angeordnet sind.

Definition: Sei A ein Alphabet. Ein Wort (eine Zeichenreihe) w über A ist eine endliche Folge

w = w₀ ... w_n-1 mit w_i Element A, n Element natürliche Zahlen ₀.

|w| = n ist die Länge des Wortes w.

Beispiel: A = {a, ..., z} , w = esel d.h. w₀ = e, w₁ = s, w₂ = e, w₃ = l und |w| = 4.

Das Wort der Länge 0 bezeichnen wir mit ε, es wird das leere Wort (die leere Zeichenreihe) genannt; d.h. |ε| = 0. Wir identifizieren ferner das Alphabet A mit der Menge der Wörter der Länge 1 über A.

Definition: Die Menge aller Wörter über einem Alphabet A wird mit A* bezeichnet:

A* = { w | w = w₀ ... w_n-1 , w_i Element A, n Element natürliche Zahlen ₀}.

Die Menge aller nichtleeren Wörter über A wird mit A⁺ bezeichnet:

A⁺ = { w | w = w₀ ... w_n-1 , w_i Element A, n Element natürliche Zahlen } = A* \ {ε}.

Satz: |A*| = hebräisches aleph ₀, d.h. es gibt abzählbar unendlich viele Wörter über A.

Definition: Seien x = x₀ ... x_n-1 und y = y₀ ... y_m-1 Wörter über einem Alphabet A. Die Verkettung xy von x und y ist definiert als das Wort

xy = x₀ ... x_n-1 y₀ ... y_m-1,

d.h. (xy)_i = x_i falls i Element {0, ..., n-1} bzw. y_i-n sonst.

Beispiel: x = bro , y = esel , xy = broesel

εx = xε = x für alle Wörter x

Die Verkettung ist eine assoziative Operation auf der Menge A*. Mit dem leeren Wort ε als neutralem Element bildet A* ein Monoid.

Definition: Die i-te Potenz eines Wortes x ist definiert durch:

x⁰ = ε,

xⁱ = x^i-1x für alle i Element natürliche Zahlen .

Definition: Sei A ein Alphabet. Eine Teilmenge L enthalten A* heißt formale Sprache oder kurz Sprache über A. Eine Sprache ist also eine beliebige Menge von gewissen Wörtern über A.

Beispiel: Es sei A = {a, b, c}. Dann sind beispielsweise folgende Mengen Sprachen über A:

L₁ = {aa, ab, aabcaacb}

L₂ = {ε}

L₃ = leere Menge

L₄ = { aⁿbⁿcⁿ | n Element natürliche Zahlen ₀}

L₅ = A* \ {abc}

Definition: Seien X und Y Sprachen, d.h. Mengen von Wörtern über A. Die Verkettung (oder das Produkt) der Sprachen X und Y ist die Sprache

XY = { xy | x Element X, y Element Y }.

Beispiel: Seien X = {a, le}, Y = {ber, bend}. Dann ist XY = {aber, abend, leber, lebend}.

Für alle Sprachen X gilt

{ε}X = X{ε} = X ,

aber

leere Menge X = X = .

Definition: Die i-te Potenz einer Sprache X ist definiert durch:

X ⁰ = {ε},

X ⁱ = X ^i-1X für alle i Element natürliche Zahlen .

Definition: Der Abschluss X* einer Sprache X ist definiert durch:

X* = Vereinigung _i IN₀ X ⁱ = {ε} vereinigt X X ² ...

Bemerkung: Fasst man das Alphabet A als Menge von Wörtern der Länge 1 auf und bildet den Abschluss A*, so erhält man die Menge aller Wörter über A, also A* aus der ursprünglichen Definition.

Satz: Sei L eine Sprache über A. Dann ist L entweder endlich oder abzählbar unendlich.

Definition: Sei A ein Alphabet. Die Menge aller Sprachen über A ist

kalligraphisches L _A = { L | L enthalten A*} = Potenzmenge (A*).