Wort-Ersetzungs-Systeme

Id: rewriting.tex,v 1.1 2006-10-16 19:50:57 waldmann Exp

Berechnungs-Modell (Markov-Algorithmen)

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

Regelmenge R $\subseteq$ $\Sigma^{*}_{}$×$\Sigma^{*}_{}$

Regel-Anwendung: u$\to_{R}^{}$v$\iff$$\exists$x, z $\in$ $\Sigma^{*}_{}$,(l, r) $\in$ R : u = x ^. l ^. z $\wedge$ x ^. r ^. z = v.

Beispiel: Bubble-Sort: {ba$\to$ab, ca$\to$ac, cb$\to$bc}

Beispiel: Potenzieren: ab$\to$bba

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