Wort-Ersetzungs-Systeme

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

Berechnungs-Modell (Markov-Algorithmen)

Regelmenge RΣ*×Σ*

Regel-Anwendung: uRv$ \iff$x, zΣ*,(l, r)∈R : u = xlzxrz = v.

Beispiel: Bubble-Sort: {baab, caac, cbbc}

Beispiel: Potenzieren: abbba

Aufgaben: gibt es unendlich lange Rechnungen für: R1 = {1000→0001110}, R2 = {aabbbbbaaa}?



Johannes Waldmann 2013-01-28