Nächste Seite: Grammatiken Aufwärts: Syntax von Programmiersprachen Vorherige Seite: Übungen Reg. Ausdr.
Berechnungs-Modell (Markov-Algorithmen)
Regelmenge
R⊆Σ*×Σ*
Regel-Anwendung:
u→Rv
Beispiel: Bubble-Sort:
{ba→ab, ca→ac, cb→bc}
Beispiel: Potenzieren:
ab→bba
Aufgaben: gibt es unendlich lange Rechnungen für:
R1 = {1000→0001110}, R2 = {aabb→bbbaaa}
∃x, z∈Σ*,(l, r)∈R : u = x⋅l⋅z∧x⋅r⋅z = v
2015-01-26