Wort-Ersetzungs-Systeme

Id: rewriting.tex,v 1.1 2011-10-11 18:13:54 waldmann Exp

Berechnungs-Modell (Markov-Algorithmen)

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

Regelmenge R⊆Σ^*×Σ^*

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

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

Beispiel: Potenzieren: ab→bba

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