imported>Boehm: typog

2022-06-13T13:58:29Z

typog

Neue Seite

'''Semi-Thue-System''' (oder auch '''Umformungssystem''', '''Wortersetzungssystem''' oder '''Stringersetzungssystem''') ist in der [[Theoretische Informatik|Theoretischen Informatik]] ein Regelsystem zur Transformation von [[Wort (Theoretische Informatik)|Wörtern]]. Anders als bei [[Formale Grammatik|formalen Grammatiken]] liegt aber nur ein Alphabet mit Ersetzungsregeln vor, es wird nicht zwischen [[Terminalsymbol]]en und [[Nichtterminalsymbol]]en unterschieden und es gibt kein Startsymbol.

Motiviert durch [[David Hilbert]]s [[Hilberts Liste von 23 mathematischen Problemen|Vortrag im Jahre 1900]] und die Ausführungen über eine logische Fundamentierung der [[Mathematik]] untersuchte der [[Norwegen|norwegische]] [[Mathematiker]] [[Axel Thue]] die Möglichkeiten, die reine Ableitungskalküle eröffnen, zunächst ganz grundlegend.<ref name="Informatik-Spektrum">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}}.</ref> 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 [[Ableitung (Informatik)|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-Hierarchie|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.

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

Oft versteht sich <math>\Sigma</math> von allein, dann benennt man ggf. auch nur <math>S</math>.

Die damit auf <math>\Sigma^*</math> bestimmte, ''einschrittige'' Ableitungsrelation <math>\Longrightarrow_S</math>, formal ebenfalls eine Teilmenge von <math> \Sigma^* \times \Sigma^* </math>, ist so definiert:

* <math>w_1\Longrightarrow_S w_2</math>, genau dann, wenn es Wörter <math> \alpha, \beta \in \Sigma^*</math> gibt und dazu irgendein <math> u\rightarrow v\in S</math>, so dass die Zerlegungen <math>w_1 = \alpha u \beta</math> und <math>w_2 = \alpha v \beta</math> gelten. Es muss also <math>\alpha</math> Präfix von sowohl <math>w_1</math> wie <math>w_2</math>, <math>\beta</math> entsprechend bei beiden Suffix sein, und die Teile von <math>w_1</math> und <math>w_2</math> dazwischen müssen gerade eine nach <math>S</math> zulässige Substitution bilden.

Eine Ableitung gemäß <math>S</math> 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 <math>\Longrightarrow_S</math> allein bestimmten Relation.

Den Ableitungen in exakt <math>n\in \mathbb{N}_0</math> Schritten entsprechen die Relationen <math>\Longrightarrow_S^n</math>:
* <math>\Longrightarrow_S^0 \quad := \quad id_{\Sigma^*}</math>
:: <math>id_{\Sigma^*}</math> ist dabei die identische Relation auf <math>\Sigma^*</math> (bei 0 Schritten sind Anfangs- und Resultat-Zeichenkette stets gleich)
* <math>\Longrightarrow_S^1 \quad := \quad \Longrightarrow_S</math>
* <math>\Longrightarrow_S^n \quad := \quad \Longrightarrow_S \circ \Longrightarrow_S^{n-1}</math> für <math>n\in \mathbb{N}, n \ge 2</math>
:: (eine n-schrittige Ableitung entsteht aus einer (n-1)-schrittigen durch Weitergehen um eine einschrittige)
Den Ableitungen in ''beliebig'' vielen Schritten entspricht die Relation
* <math>\Longrightarrow_S^* \quad := \quad \{ (x,y) |\, \exists_{n \in \mathbb{N}_0} \,x \Longrightarrow_S^n y\}</math>, es ist in relationentheoretischer Sprechweise gerade die [[reflexiv-transitive Hülle]] von <math>\Longrightarrow_S</math>.

Der Index <math>S</math> wird oft weggelassen, wenn <math>S</math> aus dem Zusammenhang eindeutig ist.

== Thue-System ==

Wenn ein Semi-Thue-System [[Symmetrische Relation|symmetrisch]] ist, d. h. wenn mit <math>(x,y)\in S</math> stets auch <math>(y,x)\in S</math> 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 <math>(\Sigma,S)</math> ein Wort <math>u</math> in ein Wort <math>v</math> umgeformt werden kann, heißt das [[Wortproblem]] des Systems <math>(\Sigma,S)</math>.

== Einzelnachweise ==
<references/>

[[Kategorie:Theorie formaler Sprachen]]
[[Kategorie:Compilerbau]]
[[Kategorie:Mathematische Logik]]
[[Kategorie:Logikkalkül]]

Semi-Thue-System - Versionsgeschichte

imported>Boehm: typog