Wort


Ein Wort setzt sich aus Zeichen eines Alphabet zusammen. Damit ist ein Wort nichts anderes als eine Folge an Zeichen aus einem Alphabet A. Man spricht deshalb auch von einem Wort über einem Alphabet A. Eine Sprache kann aus unendlichen Wörtern bestehen, Wörter selbst weisen aber eine endliche Länge auf. Die Länge eines Wortes w=a1, a2, a3, … , an heißt n und wird auch mit |w| bezeichnet. Sei w=“hallo“, dann ist |w|=5. Wie man sieht, werden Zeichen die im Wort mehrfach vorkommen auch entsprechend mehrfach gezählt.

Bei einem Alphabet Σ mit dem Zeichenvorrat Σ unterscheidet sich Σ+ zwischen Σ* dadurch, dass Σ* auch das leere Wort enthält. Das leere Wort hat die Länge 0 und wird mit dem griechischen Buchstaben ε (Epsilon) bezeichnet.

Geht man nun beispielsweise von folgenden Alphabet A = {a,b} aus. Dann ist die Menge aller Wörter einer festen Länge n über diesem Alphabet A gleich An. Weiter gilt beispielsweise: Und allgemein gilt:
A* bei Woertern

Konkatenation von Wörtern

Eine wichtige binäre Operation für Wörter ist die sogenannte Konkatenation, also die Verkettung von mehreren Wörtern. Das Operationssymbol ist im Normalfall wie bei einer Multiplikation von Zahlen der Punk „⋅“. Möchte man also die beiden Wörter: BIER und KRUG konkatenieren dann schreibt man:
BIER ⋅ KRUG = BIERKRUG

Präfix

Der Präfix eines Wortes ist ein Teilwort am Anfang diesen Wortes. Dabei ist das leere Wort ein Präfix jedes beliebigen Wortes. Demnach hat ein Wort der Länge n genau (n+1) Präfixe.

Das Wort abc hat beispielsweise folgende Präfixe:
  1. ε
  2. a
  3. ab
  4. abc

Suffix

Der Suffix eines Wortes ist ein Teilwort am Ende dieses Wortes. Wie auch beim Präfix, ist das leere Wort ein Suffix jedes beliebigen Wortes.


Zitat:



Edsger Wybe Dijkstra:

"Als es noch keine Computer gab, gab es auch das Programmieren als Problem nicht. Als es dann ein paar leistungsschwache Computer gab, wurde das Programmieren zu einem kleinen Problem und nun, wo wir leistungsstarke Computer haben, ist auch das Programmieren zu einem riesigen Problem angewachsen. In diesem Sinne hat die elektronische Industrie kein einziges Problem gelöst, sondern nur neue geschaffen." - The Humble Programmer, ACM Turing Lecture 1972