Wort-Ersetzungs-Systeme

mathend000#Id mathend000#

Berechnungs-Modell (Markov-Algorithmen)

• Zustand (Speicherinhalt): Zeichenfolge (Wort)
• Schritt: Ersetzung eines Teilwortes

Regelmenge R⊆Σ^*×Σ^* mathend000#

Regel-Anwendung: u→_Rv$\iff$∃x, z∈Σ^*,(l, r)∈R : u = x⋅l⋅z∧x⋅r⋅z = v mathend000#.

Beispiel: Bubble-Sort: {ba→ab, ca→ac, cb→bc} mathend000#

Beispiel: Potenzieren: ab→bba mathend000#

Aufgaben: gibt es unendlich lange Rechnungen für: R₁ = {1000→0001110}, R₂ = {aabb→bbbaaa} mathend000#?