Beispiel
Wort (1) v = abc
Wort (2) w = aeb
Ableitungsregeln:
(1) ab -> ad
(2) dc -> ee
(3) e -> b
(4) ad -> ae
(5) eb -> b
(6) abc -> e
v => w:abc
Wir versuchen den längsten Ausdruck zu matchen. In diesem Fall wäre das (6).
v => w:e
Aus e können wir nach (3) nur noch b herleiten. Und aus b sind keine Ableitungsregeln vorhanden. Also verwerfen wir diesen Weg und suchen weiter.
v => w:abc
In der Reihenfolge [ab,b,a,b,c] suchen wir nach weiteren Treffern.
Mit (1) existiert nur ein Weg, der uns weiterbringt. Wir bilden adc und können die Alternativen verwerfen, da es bis hierher nur diesen einen Weg gibt.
v => w:adc
Wir arbeiten wieder unsere Liste [adc,ad,dc,a,d,c] ab. Mit (4) gibt es eine Produktion die in aec resultiert und mit (2) eine weitere die aee ergibt. Wir werden beide versuchen. Zuerst wollen wir mit aec weiterarbeiten bis es entweder nicht weitergeht oder wir am Ziel sind.
v => w:aec
Wenn wir uns die Liste [aec,ae,ec,a,e,c] anschauen, merken wir, dass nur e weiterführt. Das führt zu einem b. Das resultierende abc wäre aber wieder das selbe Wort wie am Anfang. Es handelt sich also um einen Zyklus.
Wir erinnern uns wieder an aec und fahren damit fort.
Da es ein e unter den Ableitungsregeln gibt, das auf b zeigt, brauchen wir nur noch (3) auf das letzte 'e' anzuwenden und wir haben das Ziel erreicht.
v => w:aeb
Hinweis zum allgemeinen Wortproblem?:
Wie ihr in diesem Beispie gesehen habt, kann man auf Zyklen treffen. Somit gibt es nicht nur einen Weg, sondern auch die Wege, die über Zyklen führen und erst später zum Ziel kommen.
Wort w ist durch Regelsystem darstellbar, aber wegen einseitiger Ersetzungsrichtung alpha -> beta nur in eine Richtug. Daher auch die Bezeichnung Semi-... .
