Pfeile

Disclaimer: Dieser Thread wurde aus dem alten Forum importiert. Daher werden eventuell nicht alle Formatierungen richtig angezeigt. Der ursprüngliche Thread beginnt im zweiten Post dieses Threads.

Pfeile
Könnte mir bitte nochmal jemand erklären, was die verschiedenen Pfeile bedeuten?
Also
→⁰
→⁺
→*
(und andere?)


Da der Kontext hier nicht wirklich ersichtlich ist, einfach mal was allgemeingültiges:

  • steht für mindestens eins, ansonsten beliebige Anzahl
    
  • steht unbeschränkt für beliebige Anzahl
    

Ich vermute es geht dir um soetwas wie Produktionen.


Ich versuchs mal (ohne Garantie):
→⁰ ist das TES (eine Relation), also quasi die Menge der Regeln die das TES bilden.
→⁺ und →* stehen für das mehrmalige Anwenden einer Regel aus dem TES. Wobei, wie schon geschrieben, das + für mind. ein mal und das * für beliebig oft steht.
t →* s bedeutet also dass es eine Ableitungskette beliebiger Länge gibt, mit der man von Term t nach Term s kommt. Du musst also evtl. mehrere Regeln des TES hintereinander ausführen um von t nach s zu kommen.


Auch noch zu erwähnen ist die Relation →, also “Ein Reduktionsschritt”. Dann ist…

  • → der kontext- und stabile (d.h. Abschluss unter Substitution) Abschluss von →⁰
  • →⁺ der transitive Abschluss von →
  • →* der reflexive Abschluss von →⁺, d.h. der transitiv-reflexive Abschluss von →

Siehe auch die Erklärung ab 00:35 in der Aufzeichung der ersten Übung (15.04.2014).