Theoretische Informatik

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  ₀ }.

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} }

Die Menge aller Wörter der Länge 1 über A wird mit A¹ bezeichnet:

A¹   =   { x  |  x = x₀ ... x_n-1 ,  x_i  A,  n  {1} }   =   A^? \ {ε}.

 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.

Sprachen werden hier nur unter formalen Gesichtspunkten betrachtet; es wird keinerlei Bedeutung mit den Wörtern der Sprache verbunden.

L₁  =  {aa, ab, aabcaacb}

L₂  =  {a, b}

L₃  =  {ε}

L₄  =  

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

L₆  =  A*

Die Sprachen L₁, L₂, L₃ und L₄ enthalten endlich viele Wörter, die Sprachen L₅ und L₆ unendlich viele. Zu beachten ist der Unterschied zwischen L₃ und L₄. Die Sprache L₃ enthält ein Wort, nämlich das leere Wort ε, die Sprache L₄ enthält kein Wort. Die Sprache L₂ enthält nur Wörter der Länge 1; eine solche Sprache bezeichnen wir als Elementarsprache.

Elementarsprache.

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

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

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

{aber, abend, ader, leber, lebend, leder}

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

aber

X  =  X  =  .

X ⁰  =  {ε},

X ⁱ  =  X ^i-1X   für alle  i  .

X*   =    _i  IN0   X ⁱ   =   {ε}      X      X ²     ...

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ünglichen Definition.

Z   eine endliche, nichtleere Menge von Zuständen, A   das Eingabealphabet, d   die Übergangsrelation   d    ZAZ, q  Z      der Startzustand, F  Z   die Menge der Endzustände.

Ein deterministischer endlicher Automat ist ein Spezialfall des nichtdeterministischen endlichen Automaten, bei dem die Übergangsrelation eine Übergangsfunktion ist:

d : ZA  Z