Informatiker Board | formale Sprachen | Semi-Thue-System! Was ist das?

Informatiker Board » Themengebiete » Theoretische Informatik » formale Sprachen » Semi-Thue-System! Was ist das?

» Hallo Gast [Anmelden|Registrieren]

Letzter Beitrag | Erster ungelesener Beitrag

Druckvorschau | An Freund senden | Thema zu Favoriten hinzufügen

Semi-Thue-System! Was ist das?

Autor

Beitrag

« Vorheriges Thema | Nächstes Thema »

informadigg
Grünschnabel

Dabei seit: 11.03.2015
Beiträge: 3

Semi-Thue-System! Was ist das?

Zitatantwort auf diesen Beitrag erstellen

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

informadigg hat dieses Bild (verkleinerte Version) angehängt:

11.03.2015 10:07

Nehmen Sie informadigg in Ihre Freundesliste auf

Karlito Karlito ist männlich

Kaiser

Dabei seit: 11.04.2011
Beiträge: 1.461

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

Gruß,

Karlito

11.03.2015 11:04

Nehmen Sie Karlito in Ihre Freundesliste auf

informadigg
Grünschnabel

Dabei seit: 11.03.2015
Beiträge: 3

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

Dieser Beitrag wurde 1 mal editiert, zum letzten Mal von informadigg: 11.03.2015 12:29.

11.03.2015 12:26

Karlito Karlito ist männlich

Kaiser

Dabei seit: 11.04.2011
Beiträge: 1.461

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

11.03.2015 13:53

informadigg
Grünschnabel

Dabei seit: 11.03.2015
Beiträge: 3

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

11.03.2015 14:45

Karlito Karlito ist männlich

Kaiser

Dabei seit: 11.04.2011
Beiträge: 1.461

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

11.03.2015 18:32

Baumstruktur | Brettstruktur

Informatiker Board » Themengebiete » Theoretische Informatik » formale Sprachen » Semi-Thue-System! Was ist das?