Theoretische Informatik

Definition:  Ein Alphabet ist eine endliche, nichtleere Menge von Zeichen. Ein geordnetes Alphabet ist ein Alphabet, dessen Zeichen gemäß einer Ordnungs­relation angeordnet sind.

Beispiel:  Die folgenden Mengen sind Beispiele für Alphabete:

A₀  =  {a, b}

A₁  =  {a, ..., z}   (Klein­buchstaben)

A₂  =  { ·, –, }   (Morsezeichen: kurz, lang, Pause)

A₃  =  { t, c, a, g }   (DNA-Basen)

A₄  =  { a, ..., z, ä, ö, ü, ß, A, ..., Z, Ä, Ö, Ü, , -, ., ,, !, ?, : }
(Buchstaben, Umlaute, Leerzeichen, Satzzeichen)

A₁ ist ein geordnetes Alphabet, gemäß der gewöhnlichen alpha­betischen Ordnung der Buchstaben.

Definition:  Sei A ein Alphabet. Ein Wort x über A ist eine endliche Folge

x  =  x₀ ... x_n-1     mit  x_i ∈ A,   n ∈ ℕ₀

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

Das Wort der Länge 0 bezeichnen wir mit ε, es wird das leere Wort genannt.

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

Definition:  

Die Menge aller Wörter der Länge n, n ∈ ℕ₀, über A wird mit Aⁿ bezeichnet:

Aⁿ   =   { x  |  x =  x₀ ... x_n-1 ,  x_i ∈ A }

Beispiel:  Für das Alphabet A = {a,b} ist A³ die folgende Menge von Wörtern:

A³  =  { aaa, aab, aba, abb, baa, bab, bba, bbb }

Definition:  

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

A*   =  { x  |  x = x₀ ... x_n-1 ,  x_i ∈ A,  n ∈ ℕ₀ }

Definition:  

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

A⁺   =   { x  |  x = x₀ ... x_n-1 ,  x_i ∈ A,  n ∈ ℕ }   =   A* \ {ε}

Die Menge aller Wörter der Länge höchstens 1 über A wird mit A^? bezeichnet:

A^?   =   { x  |  x = x₀ ... x_n-1 ,  x_i ∈ A,  n ∈ {0, 1} }   =   A⁰  ∪  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 ∈ {0, ..., n-1}   bzw.   y_i-n sonst.

Die Wörter x und y werden also einfach hinter­einander­geschrieben und ergeben so das neue Wort xy.

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

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

x⁰  =  ε,

xⁱ  =  x^i-1x   für alle  i ∈ ℕ.

Eine Potenz von x entsteht also, indem das Wort x mit sich selbst verkettet wird.

Beispiel:  Sei x = bla. Dann ist

x³  =  blablabla.

Definition:  Sei A ein Alphabet. Eine Teilmenge L ⊆ A* heißt 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 beispiels­weise folgende Mengen Sprachen über A:

L₁  =  {aa, ab, aabcaacb}

L₂  =  {a, b}

L₃  =  {ε}

L₄  =  ∅

L₅  =  {aⁿbⁿcⁿ | n ∈ ℕ₀}

L₆  =  A*

Definition:  Sei A ein Alphabet und sei A¹ die Menge aller Wörter der Länge 1 über A. Eine Teilmenge von A¹ nennen wir eine Elementar­sprache.

Beispiel:  Sei A = {a, b, c}. Dann gibt es acht Elementar­sprachen über A, nämlich

∅,  {a},  {b},  {c},  {a, b},  {a, c},  {b, c},  {a, b, c}

Definition:  Sei A ein Alphabet und sei L eine Sprache über A. Das Komplement L der Sprache L besteht aus allen Wörtern über A, die nicht in L liegen, d.h.

L   =   A* \ L   =   { w ∈ A*  |  w ∉ L }

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 ∈ X,  y ∈ Y }

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

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

X ⁰  =  {ε}

X ⁱ  =  X ^i-1X   für alle  i ∈ ℕ

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

X*   =    _i ∈ ℕ0   X ⁱ   =   {ε}   ∪   X   ∪   X ²   ∪  ...

Beispiel:  Sei X = { bla }. Dann ist

X*  =  { ε, bla, blabla, blablabla, ... }

Sei X = { du, bi }. Dann ist

X*  =  { ε, du, bi, dudu, dubi, bidu, bibi, dududu, dubidu, ... }

Bemerkung:  Fasst man das Alphabet A als Menge aller Wörter 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üng­lichen Definition.