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

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

» Hallo Gast [Anmelden|Registrieren]

Antwort erstellen

Benutzername:

(du bist nicht eingeloggt!)

Thema:

Nachricht:

HTML ist nicht erlaubt
BBCode ist erlaubt
Smilies sind erlaubt
Bilder sind erlaubt

Smilies: 21 von 33

einfacher Modus erweiterter Modus

aktuellen Tag schließen

alle Tags schließen

Spamschutz:
Text aus Bild eingeben

URLs automatisch umwandeln: fügt automatisch [url] und [/url] in Internet-Adressen ein.
Smilies in diesem Beitrag deaktivieren.
BBCode in diesem Beitrag deaktivieren.
Bilder in diesem Beitrag deaktivieren.
Signatur anzeigen: Soll die im Profil eingestellte Signatur an den Beitrag angehangen werden?
Nachrichtenlänge überprüfen

Die letzten 6 Beiträge
Karlito	Genau gesagt, beschreibt es das Ersetzungssystem selbst und einige Notationen, wie das Ersetzungssystem notiert werden kann.
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!
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
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
Karlito	Was genau verstehst du denn nicht? Sind Begriffe unklar? Kannst Du dir nur das Ergebnis der Definition nicht vorstellen? Gruß, Karlito
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 :-) informadigg hat dieses Bild (verkleinerte Version) angehängt: