Informatiker Board | Druckvorschau: Semi-Thue-System! Was ist das?

Informatiker Board (http://www.informatikerboard.de/board/index.php)
- Themengebiete (http://www.informatikerboard.de/board/board.php?boardid=1)
--- Theoretische Informatik (http://www.informatikerboard.de/board/board.php?boardid=5)
---- formale Sprachen (http://www.informatikerboard.de/board/board.php?boardid=12)
----- Semi-Thue-System! Was ist das? (http://www.informatikerboard.de/board/thread.php?threadid=2160)

Geschrieben von informadigg am 11.03.2015 um 10:07:

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 :-)

Geschrieben von Karlito am 11.03.2015 um 11:04:

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

Gruß,

Karlito

Geschrieben von informadigg am 11.03.2015 um 12:26:

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

Geschrieben von Karlito am 11.03.2015 um 13:53:

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

Geschrieben von informadigg am 11.03.2015 um 14:45:

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

Geschrieben von Karlito am 11.03.2015 um 18:32:

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