Theoretische Informatik

Alphabet, Wort, Sprache

 aufwärts

Alphabet

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:

A0  =  {a, b}

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

A2  =  { ·, –, Leerzeichen }   (Morsezeichen: kurz, lang, Pause)

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

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

 

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

Wort

Aus Zeichen werden als nächstes Wörter gebildet.

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

x  =  x0 ... xn-1     mit  xi Element A,   n Element natürliche Zahlen0.

|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.   x0 = e,  x1 = s,  x2 = e,  x3 = l   und |x| = 4.

Anstelle des Begriffs Wort werden gelegentlich auch die Bezeich­nungen Zeichenkette, Zeichenfolge oder Zeichenreihe verwendet.

In der umgangs­sprachlichen Bedeutung enthält ein Wort keine Leerzeichen – sonst sind es mehrere Wörter. Dagegen ist nach der angegebenen Definition ein Wort einfach eine endliche Folge von Alphabet­zeichen, und wenn das Leerzeichen im Alphabet vorkommt (so wie in A4), dann kann es auch in einem Wort vorkommen. Und wenn Satzzeichen im Alphabet vorkommen (so wie in A4), so können auch diese in einem Wort vorkommen.

Insofern wird nicht unter­schieden zwischen den umgangs­sprachlichen Begriffen Wort, Satz und Text – die Bibel etwa ist ein einziges (sehr langes) Wort über einem bestimmten zugrunde­liegenden Alphabet.

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

A*   =  { x  |  x = x0 ... xn-1xi Element An Element natürliche Zahlen0 }.

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

A+   =   { x  |  x = x0 ... xn-1xi Element An Element natürliche Zahlen }   =   A* \ {ε}.

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

A?   =   { x  |  x = x0 ... xn-1xi Element An Element {0, 1} }

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

A1   =   { x  |  x = x0 ... xn-1xi Element An Element {1} }   =   A? \ {ε}.

Alphabet­zeichen und Wörter der Länge 1 sind schwer zu unter­scheiden. Daher ist es sinnvoll, das Alphabet A mit der Menge A1 der Wörter der Länge 1 über A zu identifizieren.

Verkettung von Wörtern

Definition:  Seien  x = x0 ... xn-1  und  y = y0 ... ym-1  Wörter über einem Alphabet A. Die Verkettung  xy  von  x  und  y  ist definiert als das Wort

xy   =   x0 ... xn-1 y0 ... ym-1,

d.h.   (xy)i  =  xi   falls  i Element {0, ..., n-1}   bzw.   yi-n sonst.

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

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

Für alle Wörter x gilt

εx = xε = x.

Für die Länge des Wortes xy, das durch Verkettung der Wörter x und y entsteht, gilt

|xy|  =  |x| + |y|

Wenn wir ein Wort x Element A* mit einem Zeichen a Element A verketten wollen, fassen wir a als Wort der Länge 1 auf, denn die Verkettung ist eigentlich nur für Wörter definiert.

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:

x0  =  ε,

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

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

Beispiel:  Sei x = bla. Dann ist

x3  =  blablabla.

Sprache

Aus Wörtern werden als nächstes Sprachen gebildet.

Definition:  Sei A ein Alphabet. Eine Teilmenge L enthalten in 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 Gesichts­punkten betrachtet; es wird keinerlei Bedeutung mit den Wörtern der Sprache verbunden.

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

L1  =  {aa, ab, aabcaacb}

L2  =  {a, b}

L3  =  {ε}

L4  =   leere Menge 

L5  =  { anbncn  |  n Element natürliche Zahlen0 }

L6  =  A*

Die Sprachen L1L2L3 und L4 enthalten endlich viele Wörter, die Sprachen L5 und L6 unendlich viele. Zu beachten ist der Unterschied zwischen L3 und L4. Die Sprache L3 enthält ein Wort, nämlich das leere Wort ε, die Sprache L4 enthält kein Wort. Die Sprache L2 enthält nur Wörter der Länge 1; eine solche Sprache bezeichnen wir als Elementar­sprache.

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

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

 leere Menge ,  {a},  {b},  {c},  {a, b},  {a, c},  {b, c},  {a, b, c}

Operationen auf Sprachen

Sprachen sind Mengen, daher sind die Operationen Vereinigung, Durchschnitt und Differenz bei Sprachen genauso wie bei Mengen definiert. Weitere wichtige Operationen sind das Komplement einer Sprache, die Verkettung von zwei Sprachen sowie der Abschluss einer Sprache. Diese Operationen werden im Folgenden erklärt.

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 Element A*  |  w nicht Element 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 Element Xy Element Y }.

Die Sprache XY entsteht also, indem jedes Wort der Sprache X mit jedem Wort der Sprache Y verkettet wird.

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

Für alle Sprachen X gilt

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

aber

 leere Menge X  =  X leere Menge   =   leere Menge .

Durch Verkettung einer Sprache mit sich selbst entstehen Potenzen der Sprache.

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

X 0  =  {ε},

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

Eine außerordentlich wichtige Operation ist der Abschluss einer Sprache.

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

X*   =   Vereinigung i Element IN0   X i   =   {ε}   vereinigt   X   vereinigt   X 2   vereinigt  ...

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.

 

Weiter mit:   [Mächtigkeit der Menge aller Wörter und der Menge aller Sprachen]   oder   up

 

homeH.W. Lang   Hochschule Flensburg   lang@hs-flensburg.de   Impressum   ©   Created: 09.12.1997   Updated: 13.05.2016
Valid HTML 4.01 Transitional


Campus Flensburg

Informatik in Flensburg studieren...

 

Neu gestaltetes Studienangebot:

Bachelor-Studiengang
Angewandte Informatik

mit Schwerpunkten auf den Themen Software, Web, Mobile, Security und Usability.

Ihr Abschluss
nach 7 Semestern:
Bachelor of Science

 

Ebenfalls ganz neu:

Master-Studiengang
Angewandte Informatik

Ein projektorientiertes Studium auf höchstem Niveau mit den Schwerpunkten Internet-Sicherheit, Mobile Computing und Human-Computer Interaction.

Ihr Abschluss
nach 3 Semestern:
Master of Science

 

Weitere Informatik-Studienangebote an der Hochschule Flensburg:

Medieninformatik

Wirtschaftsinformatik