Komplement durch SemiThue

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.

Komplement durch SemiThue
TheoInf II SS 2004, Aufgabe 5b) Gefragt: ein Semi-Thue System, das zu
einer Zahl das Einerkomplement berechnet.
Lösung: a0 → 1aa1 → 0aaa → e

Wenn ich das versuche, funktioniert es aber nicht:

111111 ← 2^6-1
-101010 ← Zahl

1010101 ← gewolltes Ergebnis (richtig)

Aber jetzt mit dem Semi-Thue System:
a0->1aa1 müsste doch schon ergeben:

101010 ← Zahl

1111 ← gewolltes Ergebnis (durch Semi-Thue System erstellt)

Irgendwas muss ich falsch machen :frowning:
Kann mir jemand schrittweise vorführen, wie das richtige Ergebnis hergeleitet wird?
Danke im Voraus.


Korrekte Lösung: a0 → 1a; a1 → 0a; aa → e

Ich denke das ist einfach nur ein Tippfehler in der Lösung. So kann man sich die Funktionsweise denke ich recht schnell klar machen, wenn man als Eingabe awa betrachtet, wobei w das zu invertierende Wort darstellt.


g ja, die haben nur die leerzeichen vergessen!