Wort__theoretische_Informatik_
Wort__theoretische_Informatik_

=== Spiegelung ===
Die Spiegelung oder das Reverse  eines Wortes  ergibt sich, wenn man  rückwärts schreibt. 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:
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.