Semi-Thue-System

Semi-Thue-System (oder auch Umformungssystem, Wortersetzungssystem oder Stringersetzungssystem) ist in der Theoretischen Informatik ein Regelsystem zur Transformation von Wörtern. Anders als bei formalen Grammatiken liegt aber nur ein Alphabet mit Ersetzungsregeln vor, es wird nicht zwischen Terminalsymbolen und Nichtterminalsymbolen unterschieden und es gibt kein Startsymbol.

Motiviert durch David Hilberts Vortrag im Jahre 1900 und die Ausführungen über eine logische Fundamentierung der Mathematik untersuchte der norwegische Mathematiker Axel Thue die Möglichkeiten, die reine Ableitungskalküle eröffnen, zunächst ganz grundlegend.[1] Aus diesen Untersuchungen hat sich der heutige Begriff des Thue-Systems und des Semi-Thue-Systems herausgebildet.

Die auch in der Logik häufig verwendeten Ableitungs-Kalküle stammen von Emil Leon Post (1936) und als Ersetzungssysteme für Zeichenketten schließlich schon 1914 von Axel Thue. Die Thue-Systeme bilden den Ausgangspunkt zur Definition von Chomsky-Grammatiken; sie verallgemeinern das Prinzip der Ersetzung von Einzelsymbolen in Zeichenketten auf die Ersetzung ganzer Teilzeichenketten.

Eine zulässige Ersetzung nach einem bestimmten Semi-Thue-System besteht darin, in einer vorliegenden Zeichenkette eine bestimmte Teilzeichenkette vorzufinden und diese durch eine bestimmte andere zu substituieren. Das Paar aus ersetzender und ersetzter Teilzeichenkette nennt man Substitution, die Menge aller Substitutionen, die man zulässt, bestimmt zusammen mit dem Zeichenalphabet das spezifische Semi-Thue-System.

DefinitionenBearbeiten

Ein Semi-Thue-System (STS) ist ein Alphabet   zusammen mit einer Menge von Substitutionen, die man gewöhnlich als   schreibt, wobei u und v jeweils Wörter über   sind. Formaler ist ein Semi-Thue System also ein Paar   aus einem Alphabet   und einer Menge S von Substitutionen  . Dabei bezeichnet   die Menge aller möglichen Wörter, die man mit Buchstaben aus   bilden kann (einschließlich des leeren Wortes aus 0 Buchstaben).

Oft versteht sich   von allein, dann benennt man ggf. auch nur  .

Die damit auf   bestimmte, einschrittige Ableitungsrelation  , formal ebenfalls eine Teilmenge von  , ist so definiert:

  •  , genau dann, wenn es Wörter   gibt und dazu irgendein  , so dass die Zerlegungen   und   gelten. Es muss also   Präfix von sowohl   wie  ,   entsprechend bei beiden Suffix sein, und die Teile von   und   dazwischen müssen gerade eine nach   zulässige Substitution bilden.

Eine Ableitung gemäß   wird sich i.a. aus mehreren Einzelschritten zusammensetzen, die immer sukzessive auf dem Resultat des jeweils vorigen vorgenommen werden. Anfangszeichenkette und mit diesem Vorgehen mögliche Resultate stehen dann ebenfalls in einer durch   allein bestimmten Relation.

Den Ableitungen in exakt   Schritten entsprechen die Relationen  :

  •  
  ist dabei die identische Relation auf   (bei 0 Schritten sind Anfangs- und Resultat-Zeichenkette stets gleich)
  •  
  •   für  
(eine n-schrittige Ableitung entsteht aus einer (n-1)-schrittigen durch Weitergehen um eine einschrittige)

Den Ableitungen in beliebig vielen Schritten entspricht die Relation

  •  , es ist in relationentheoretischer Sprechweise gerade die reflexiv-transitive Hülle von  .

Der Index   wird oft weggelassen, wenn   aus dem Zusammenhang eindeutig ist.

Thue-SystemBearbeiten

Wenn ein Semi-Thue-System symmetrisch ist, d. h. wenn mit   stets auch   ist, dann nennt man es auch Thue-System. Jede Regel ist hier auch in die Gegenrichtung anwendbar.

Die Frage, ob mit einem Semi-Thue-System   ein Wort   in ein Wort   umgeformt werden kann, heißt das Wortproblem des Systems  .

EinzelnachweiseBearbeiten

  1. Wolfgang Thomas: „When nobody else dreamed of these things“ – Axel Thue und die Termersetzung. In: Informatik Spektrum. Volume 33, Number 5, S. 504–508, doi:10.1007/s00287-010-0468-9.