[informatik-bonn] Re: Aufgabe 1

  • From: Thorsten Horstmann <Thorsten.Horstmann@xxxxxx>
  • To: informatik-bonn@xxxxxxxxxxxxx
  • Date: Sun, 22 Jun 2003 23:39:51 +0200

Hi,

Lutz Oberst wrote:

Wie hast du das denn genau gemacht? Ich wollte das auch so
machen, bin aber daran gescheitert, daß ich die Position
des Partnersymbols zu w_i nicht eindeutig speichern kann.
Speichere ich i direkt, kann ich nicht wissen wie weit ich von
der Mitte entfernt bin und folgendes kann passieren:
[snip]

Ich wüßte also nicht wie ich den jeweils relevanten Partner
zu einem Symbol finden sollte. Wie hast du das hinbekommen?

der "relevanten Partner" kann natuerlich auch nur nicht-deterministisch gefunden werden. Nachdem ich w_i gelesen habe, lese ich erst einmal i weitere Zeichen. Der Lesekopf steht also auf w_(2i). Wegen w_(i+n) = w_(2i+(n-i)) muss der Automat dann n-i erraten. Dazu liest er j Zeichen und wenn w_(2i+j) != w_(i) ist _und_ noch 2i+j Zeichen zu lesen sind dann wird das Wort akzeptiert.

HTH,
  -Thorsten

PS: Hast Du Ideen fuer die a) oder c) ?


Other related posts: