Wort (theoretische Informatik)

endliche Folge von Symbolen eines Alphabets in der theoretischen Informatik
(Weitergeleitet von Spiegelung (Wort))

In der theoretischen Informatik ist ein Wort eine endliche Folge von Symbolen eines Alphabets. Im Gegensatz zur natürlichsprachlichen Bedeutung von Wörtern, die stets eine eigenständige Bedeutung haben, bezeichnet der Ausdruck Wort in der theoretischen Informatik lediglich eine Zeichenkette und nicht deren mögliche Bedeutung.

Wörter oder Worte[1] sind die Elemente einer formalen Sprache. Sie sind deshalb wichtig für mathematische Modellierungen, für die Theorie der Programmiersprachen, für die Berechenbarkeitstheorie und andere Gebiete der theoretischen Informatik.

Definition

Bearbeiten

Es sei   ein gegebenes Alphabet und   eine natürliche Zahl aus  , der Menge der natürlichen Zahlen einschließlich der Null ( ). Ein Wort   der Länge   ist eine endliche Folge   mit   für alle  .

Die Länge   eines Wortes   wird als   notiert; die Zahl, wie oft das Zeichen   im Wort   vorkommt, mit  .[2][3] Ein besonderes Wort ist das leere Wort, das aus keinem Symbol besteht (die Länge 0 besitzt) und meist mit dem griechischen Buchstaben   (Epsilon) dargestellt wird (auch   findet man gelegentlich[4]). Die Menge aller Wörter, die man aus einem Alphabet   bilden kann, ist die Kleenesche und positive Hülle über diesem Alphabet. Diese ist die disjunkte Vereinigung

 .

Die nichtleeren Wörter sind dann entsprechend die ‚positive Hülle’

 .

Zur Angabe eines Wortes wird oft die vereinfachte Schreibweise   benutzt, was jedoch nur möglich ist, wenn das verwendete Alphabet eine eindeutige Zuordnung der benutzten Symbole zulässt. So kann diese Kurzschreibweise beim Alphabet   nicht angewendet werden, da hier zum Beispiel aus der Schreibweise   nicht eindeutig hervorgeht, ob das Wort  ,   oder   gemeint ist.

Wörter der Länge   können wie folgt aufgefasst werden:[5]

  • als endliche Folgen (Sequenz) – da Tupel als Folgen mit endlicher Länge   aufgefasst werden können
  • als Elemente des  -fachen kartesischen Produktes – da Tupel auch so aufgefasst werden können

Beispiele

Bearbeiten

Es sei   das Alphabet der lateinischen Buchstaben und  . Dann sind die Wörter   und   Beispiele für Wörter über   und   ist ein Wort über  . Man erkennt, dass   und   ist.

Operationen auf Wörtern

Bearbeiten

Konkatenation

Bearbeiten

Die Konkatenation oder Verkettung ist eine Verknüpfung zweier Wörter zu einem neuen Wort, das durch Aneinanderhängen der beiden Symbolfolgen entsteht. Die Konkatenation der beiden Wörter   und   über einem Alphabet   wird mit   oder   angegeben und ist definiert durch:

 

Dabei ist nach der Definition des Wortes   und   mit   und   für alle   und  . Nach der obigen Definition ist   ein Präfix und   ein Suffix des durch die Konkatenation entstandenen Wortes  . Die Länge eines konkatenierten Wortes entspricht dabei der Summe der Längen der einzelnen (Teil-)Wörter. So gilt für jedes Wort   und  :

 ,

und für die absolute Häufigkeit eines Zeichens  :

 .

Das neutrale Element der Konkatenation ist das leere Wort, da für jedes beliebige Wort   gilt, dass:

 

Da außerdem die Konkatenation assoziativ ist, bildet das Tripel   aus der Menge aller Wörter über einem beliebigen Alphabet  , der Verknüpfung der Konkatenation und dem leeren Wort als neutralem Element ein Monoid. Die Assoziativität bedeutet, dass ohne weiteres Klammern weggelassen werden können:

 

Demgegenüber ist die Konkatenation nicht kommutativ, d. h. nicht für alle Wörter   und   gilt, dass   ist. So ist zum Beispiel:

 

Die  -te Potenz   eines Wortes   ist definiert als die  -fache Konkatenation dieses Wortes mit sich selbst. Die Definition der Potenz wird meist rekursiv angegeben:

 
    (für  )

So sind zum Beispiel:

 
 
 

Nach der Definition der Konkatenation ist die Länge der  -ten Potenz eines beliebigen Wortes   gleich dem Produkt aus   und der Länge von  :

 ,

und für die absolute Häufigkeit eines jeden Zeichens  :

 

Spiegelung

Bearbeiten

Die Spiegelung oder das Reverse   eines Wortes   ergibt sich, wenn man   rückwärts schreibt.[6] Wenn also   ist, so ist   die endliche Folge   mit   und   für alle  . Die Länge eines Wortes ist also gleich der Länge seiner Spiegelung:

 

So gilt zum Beispiel für die folgenden Wörter:

 
 
 

Das Reverse eines Wortes lässt sich außerdem mit Hilfe der strukturellen Induktion über dem Aufbau des betreffenden Wortes definieren. Dazu definiert man im Induktionsanfang das Reverse des leeren Wortes als das leere Wort. Im Induktionsschritt definiert man das Reverse eines aus einem Teilwort und einem Symbol zusammengesetzten Wortes als die Konkatenation des Symbols mit dem Reversen des Teilwortes:

Induktionsanfang:  

Induktionsschritt:  

So lässt sich schrittweise das Reverse eines Wortes herleiten:

 
 
 

Ein Wort wie  , das identisch mit seiner Spiegelung ist, wird Palindrom genannt. Mathematisch werden diese spiegelsymmetrischen Worte als die Fixpunkte der Spiegelung R angesehen.

Präfix, Infix und Suffix

Bearbeiten

Ein Infix ist eine Hinzufügung innerhalb eines Wortes. Jede endliche Teilfolge von aufeinander folgenden Symbolen eines Wortes   wird Infix, Teilwort oder Faktor des Wortes   genannt. Ein Infix eines gegebenen Wortes   ist demnach jedes Wort  , für das es (mindestens) ein   gibt, für das gilt, dass zum einen   und zum anderen   für jedes   ist. Demnach ist ein Wort   genau dann Infix eines Wortes  , wenn gilt, dass es mindestens ein Wort   und ein Wort   aus der Kleeneschen Hülle über dem Alphabet von   gibt, so dass   ist:

  ist Infix von  

So ist das Wort   mit   ein Infix der Wörter  ,   und  , nicht aber der Wörter  ,   beziehungsweise des leeren Wortes  . In vielen Computersprachen ist für Infix die englische Bezeichnung substring gebräuchlich.

Speziell ist das leere Wort ein Infix jedes beliebigen Wortes, und jedes Wort ist ein Infix von sich selbst. Ein Infix eines beliebigen Wortes, das nicht identisch mit diesem ist, wird echtes Infix genannt.

Ein Präfix ist eine Hinzufügung am Anfang eines Wortes. Ein Präfix eines Wortes   ist demnach jedes Infix  , für das gilt, dass   und   für jedes   ist. Demnach ist   genau dann Präfix des Wortes  , wenn es mindestens ein   aus der Kleeneschen Hülle über dem Alphabet, aus dem   erzeugt wurde, gibt, so dass   ist:

  ist Präfix von  

Auch für Präfixe gilt, dass jedes Wort ein Präfix von sich selbst und das leere Wort ein Präfix jedes beliebigen Wortes ist. Ein Präfix eines Wortes, das nicht identisch mit ihm ist, wird echtes Präfix genannt.

Beispiel

Bearbeiten

Sei  , so lauten die echten Präfixe für  :

  •  
  •  
  •  
  •  
  •  
  •  .

Ein Suffix, auch Postfix genannt, ist eine Hinzufügung am Ende eines Wortes. Ein Suffix eines Wortes   ist nach der Definition des Infixes jedes Teilwort  , für das gilt, dass es ein   gibt, für das zum einen   und zum anderen   für jedes   ist. Demnach ist ein Wort   genau dann Suffix eines Wortes   mit  , wenn es mindestens ein   gibt, so dass   ist:

  ist Suffix von  

Wie für Präfixe und Infixe gilt auch für Suffixe, dass das leere Wort ein Suffix jedes beliebigen Wortes und ein beliebiges Wort stets auch ein Suffix von sich selbst ist. Ein Suffix eines Wortes, das nicht identisch mit ihm ist, wird echtes Suffix genannt.

Beispiel

Bearbeiten

Sei  , so lauten die echten Suffixe für  :

  •  
  •  
  •  
  •  
  •  
  •  .

Literatur

Bearbeiten
  • John E. Hopcroft, Jeffry D. Ullman: Einführung in die Automatentheorie, formale Sprachen und Komplexitätstheorie. 3. korrigierte Auflage. Addison-Wesley, Bonn u. a. 1994, ISBN 3-89319-744-3 (Internationale Computer-Bibliothek).
  • Katrin Erk, Lutz Priese: Theoretische Informatik. Eine umfassende Einführung. 2. erweiterte Auflage. Springer-Verlag, Berlin u. a. 2002, ISBN 3-540-42624-8, S. 27–28 (Springer-Lehrbuch).
  • Gottfried Vossen, Kurt-Ulrich Witt: Grundkurs theoretische Informatik. Eine anwendungsbezogene Einführung - für Studierende in allen Informatik-Studiengängen. 4. verbesserte und erweiterte Auflage. Vieweg, Wiesbaden 2006, ISBN 3-8348-0153-4, S. 15 (online).
  • M. Lothaire: Combinatorics on Words. Cambridge University Press, 1997, ISBN 978-0-511-56609-7, S. 1 ff., doi:10.1017/CBO9780511566097.

Anmerkungen und Einzelnachweise

Bearbeiten
  1. Gebräuchlich sind beide Pluralformen, vgl. z. B. dtv-Atlas zur Mathematik, Bd. I, ISBN 3-423-03007-0, S. 245 versus Bauer, Goos: Informatik. Bd. I, ISBN 3-540-06332-3, S. 28.
  2. Klaus Reinhardt: Prioritätszählerautomaten und die Synchronisation von Halbspursprachen, Fakultät Informatik der Universität Stuttgart; Doktorarbeit 1994 (PDF; 509 KB)
  3. Dabei ist  .
  4. Yuri L. Ershov, Eugenii A. Palyutin: Mathematical Logic. Translated from the Russian by Vladimir Shokurov. Revised from the 1979 Russian edition. Mir Publishers, Moskau 1984, S. 16 (mirtitles.org).
  5. Definition von Tupel und seine Synonyme: Encyclopedia of Mathematics: Tuple
  6. Die Spiegelung eines Wortes der Länge n ist eine spezielle selbstinverse Permutation
     .
    Die Spiegelung beliebig langer Wörter ist dann die Vereinigung  
Bearbeiten