Das Kefk Network Wiki befindet sich im Testbetrieb.

Semi-Thue-System

Aus Kefk.

Wechseln zu: Navigation, Suche

Semi-Thue-System (oder auch Umformungssystem) ist in der Theoretischen Informatik ein Regelsystem zur Manipulation von Zeichenketten, also eine formale Grammatik.

Motiviert durch David Hilberts Vortrag im Jahre 1900 und den 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. 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, denn sie erweitern den Gedanken der Symbolersetzung auf ganze Zeichenketten.

Definition

Ein Semi-Thue System (STS) über einem Alphabet Σ ist eine (endliche oder unendliche) Teilmenge S \subseteq \Sigma^* \times \Sigma^*, notiert meist als S anstelle des korrekten Tupels (Σ,S). Die Elemente (u,v)\in S nennt man Produktionen oder Ableitungsregeln und schreibt diese meistens als u \rightarrow v. Die zu S gehörende einschrittige Ableitungsrelation "\Longrightarrow_S" \subseteq \Sigma^* \times \Sigma^* wird so definiert:

  • w_1\Longrightarrow_S w_2, wenn w1 = aub und w2 = avb für a,b\in \Sigma^* sowie u\rightarrow v\in S gilt.

Die reflexiv-transitive Hülle von \Longrightarrow_S wird mit \Longrightarrow_S^* bezeichnet und ist die von S definierte Ableitungsrelation. Auf der Basis von \Longrightarrow_S werden für n\in \mathbb{N} die Relationen "\Longrightarrow_S^n" erklärt:

  • \Longrightarrow_S^n \,\,\,\,:= \,\,\,\,\Longrightarrow_S^{n-1}\circ \Longrightarrow_S,
    wobei
  • \Longrightarrow_S^0 \,\,\,\,:= \,\,\,\,Id_S


Dies beschreibt die Ableitungen in genau n Schritten.

Der Index S kann weggelassen werden, wenn S aus dem Zusammenhang eindeutig ist.

Thue-System

Wenn das Semi-Thue-System symmetrisch ist, d.h. mit (x,y)\in R ist stets auch (y,x)\in R, dann heißt das System auch Thue-System. Jede Regel ist somit beidseitig anwendbar.

Die Frage, ob mit einem Semi-Thue-System (Σ,S) ein Wort u in ein Wort v umgeformt werden kann, heißt das Wortproblem des Systems (Σ,R).

Wikipedia
 Dieses Dokument entstammt in seiner ersten oder einer späteren Version der deutschsprachigen Wikipedia. Es ist dort zu finden unter dem Stichwort Semi-Thue-System, die Liste der bisherigen Autoren befindet sich in der Versionsliste; die Originalfassung kann dort auch bearbeitet werden. Alle Texte der Wikipedia und ihre Derivate stehen unter der GNU-Lizenz für freie Dokumentation.
Von „http://www.kefk.org/wiki/Semi-Thue-System“
Persönliche Werkzeuge
Andere Sprachen