In Aufgabe 8.1.6 heißt es:

Jeder BPA-Term hat genau eine Normalform.

Nun gibt es aber das Ersetzungaxiom R1:

R1: x + y =_AC y + x

Ich habe hier ein Verständnisproblem mit den Begrifflichkeiten:

Sind x + y sowie y + x verschiedene oder gleiche Terme? Sind beides Normalformen? Werden sie als der "selbe" Term oder die "selbe" Normalform angesehen (wegen der Eindeutigkeit)?

Sind nur R3 bis R5 die "Reduktionsregeln", die bei Aufgabe 8.1.6 in das Transitionssystem eingehen sollen? Oder sollen auch für R1 und R2 Kanten existieren? (Speziell der Einbau aller Anwendungsmöglichkeiten von R1 macht das Transitionssystem nun nicht gerade kleiner…) Zudem ist R1 auch auf den ansonsten vollständig reduzierten Term immer wieder unendlich oft anwendbar (Wechsel zwischen zwei Zuständen), so dass am Ende doch aus jedem Zustand mindestens eine Kante wegführt.

Sind x + y sowie y + x verschiedene oder gleiche Terme? Sind beides Normalformen? Werden sie als der "selbe" Term oder die "selbe" Normalform angesehen (wegen der Eindeutigkeit)?

Es sind unterschiedliche Terme, die aber modulo =AC in derselben Äquivalenzklasse sind. Im Zusammenhang mit Normalformen werden sie also behandelt, als wären sie gleich.

Sind nur R3 bis R5 die "Reduktionsregeln", die bei Aufgabe 8.1.6 in das Transitionssystem eingehen sollen?

Ja. Der Graph wird so schon gross genug :)

Mal ne andere Frage: In Aufgabe 8.1.4 sollen wir die Ableitung für einen Zustandsübergang mit a ableiten.
Es gibt aber 4 verschiedene a-Kanten ( im Graphen). Darf man sich da eine aussuchen?

Ich versteh das "für t2" als "ein Übergang, der von t2 ausgeht". Damit hast Du nur noch weniger zur Auswahl - aber von denen darfst Du Dir einen aussuchen, ja.

Wie ist das eigentlich im Reduktionskalkuel definiert, wenn man zB

a(bc) + c(de) + a(bc) hat und zB Regel 3 anwenden will, um die beiden a(bd) 's zu einem zu machen.
Das zweite a(bd) steht ja nicht direkt neben dem ersten a(bd), sondern es steht ein c(de) dazwischen. Im Reduktionskalkül ist mit R3 aber nur x + x = x definiert, d.h. zwishcen dem x darf nichts stehen. Muss man dann davor erstmal R2 anwenden, um c(de) mit a(bd) zu vertauschen oder darf man das in einem Schritt reduzieren?

Die ersten beiden Regeln definieren Äquivalenzklassen von Termen, die sich nur durch Assoziativität oder Kommutativität ineinander überführen lassen. Wie Uncle Owen schon andeutete, sollte man diese Umformungen nicht in den Graphen einzeichnen, dann wird der viel zu groß. Stattdessen kann jeder Knoten des Graphen als Repräsentation einer Äquivalenzklasse dienen. Es reicht, einen Vertreter dieser Klasse aufzuschreiben. Man darf dann trotzdem die Ersetzungsregeln auf sämtliche Termvarianten in dieser Äquivalenzklasse anwenden.

Hinweis: Schreibt bei Eurer Lösung dazu, wie ihr die Knoten interpretiert. Und bemüht Euch, Knoten in Eurem Graphen zu identifizieren, die zur selben Äquivalenzklasse gehören. Ein Beispiel aus der Saalübung:

(a(b+b) + a(b+b))
| R3 | R3
(ab + a(b+b)) [latex]=_{AC}[/latex] (a(b+b) + ab)
| R3 | R3
(ab + ab)

Die beiden Terme der mittleren Zeile gehören zum selben Knoten des Graphen, da sie sich nur durch Kommutativität des Hauptoperators + unterscheiden.

Im Beispiel gibt es natürlich noch mehr Reduktionsmöglichkeiten, aber die sind aus Gründen der Übersichtlichkeit ausgelassen.

FRAGE:
was ist mit variableninstanziierung gemeint??

FRAGE:
was ist mit variableninstanziierung gemeint??

Das heißt soviel wie: Den Variablen einen Anfangswert zuweisen

Ich bin in diesem Thema nicht wirklich firm. Aber wäre das nicht die Initialisierung und die Instanziierung ist die Erschaffung einer neuen Variablen?

Darum geht's doch überhaupt nicht. Man benutzt ein Kalkül, die Regeln des Kalküls enthalten Variablen und den Variablen muss ein Wert (=ein PA-Ausdruck) zugewiesen werden.