%% -*- mode: latex; TeX-master: "compilerbau.tex"; -*-

\begin{slide}{Wort-Ersetzungs-Systeme}

\kopf{$ $Id: rewriting.tex,v 1.1 2011-10-11 18:13:54 waldmann Exp $ $}

Berechnungs-Modell (Markov-Algorithmen)
\begin{itemize}
\item Zustand (Speicherinhalt): Zeichenfolge (Wort)
\item Schritt: Ersetzung eines Teilwortes
\end{itemize}

Regelmenge $R \subseteq \Sigma^* \times \Sigma^*$

Regel-Anwendung: $u \to_R v \iff \exists x,z\in\Sigma^*, (l,r) \in R:
u = x \cdot l\cdot z \wedge x \cdot r \cdot 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_1 = \{ 1000 \to 0001110 \}, R_2= \{ aabb \to bbbaaa \}$?
\end{slide}
