Semi-Thue-System! Was ist das?

Neue Frage »

Auf diesen Beitrag antworten »
informadigg Semi-Thue-System! Was ist das?

Meine Frage:
Ich bin wirklich am verzweifeln und habe mir nur für folgende Frage hier einen Account erstellt:
Was genau ist ein Semi-Thue-System, bzw. wie könnte man es mit einfachen Worten definieren?

Meine Ideen:
Die formalen Regeln habe ich vorliegen(siehe Bild im Anhang), nur kann ich mir keinen Reim daraus machen.. Es wäre mir also eine große Hilfe, wenn das jemand für mich verständlich rüberbringen könnte :-)
 
Auf diesen Beitrag antworten »
Karlito

Was genau verstehst du denn nicht? Sind Begriffe unklar? Kannst Du dir nur das Ergebnis der Definition nicht vorstellen?

Gruß,

Karlito
Auf diesen Beitrag antworten »
informadigg

Genau, mir geht es um das Ergebnis dieser Definitionen. Also was bedeuten die genau..
Die Begriffe selbst sind mir soweit klar.

Wenn mich jetzt jemand fragen sollte, was ein Semi-Thue-System ist, könnte ich momentan lediglich diese Definitionen NENNEN. Aber nicht erklären was sie BEDEUTEN.

Danke schonmal! :-D
Auf diesen Beitrag antworten »
Karlito

Naja, die Bedeutung ist ganz einfach wie der Name schon sagt: es handelt sich um ein Ersetzungssystem. Dabei werden einfach Worte über einem Alphabet durch andere Worte ersetzt.

Die einfache Ersetzung besagt, dass wenn z.B. [latex](foo, bar) \in P[/latex] ist, foo durch diese Ersetzungsregel durch bar ersetzt wird.

Die transitive Erweiterung besagt nur, dass wenn [latex]\{(foo, bar), (bar, baz)\} \subset P[/latex] man statt [latex]foo \rightarrow bar \rightarrow baz [/latex] auch kürzer [latex]foo \rightarrow^+ baz [/latex] schreiben kann. Wobei bei der +-Notation immer mindestens eine Ersetzung erfolgen muss und beim * die identische Abbildung, d.h. [latex]bar \rightarrow^* bar[/latex] auch möglich ist.

Ich denke mal der Rest erschließt sich, oder?

Gruß,

Karlito
 
Auf diesen Beitrag antworten »
informadigg

Achso, das Semi-Thue-System beschreibt also nur, wie eine Abfolge von unterschiedlich vielen Ersetzungsschritten notiert werden kann?

Ich hatte es für ein spezielles Ersetzungssystem mit besonderen Regeln gehalten..

Vielen Dank für die Erleuchtung! Daumen hoch
Auf diesen Beitrag antworten »
Karlito

Genau gesagt, beschreibt es das Ersetzungssystem selbst und einige Notationen, wie das Ersetzungssystem notiert werden kann.
 
Neue Frage »
Antworten »


Verwandte Themen

Die Beliebtesten »
Die Größten »
Die Neuesten »