[informatik-bonn] Re: Aufgabe 1

  • From: Lutz Oberst <oberst@xxxxxxxxxxx>
  • To: informatik-bonn@xxxxxxxxxxxxx
  • Date: Sun, 22 Jun 2003 16:48:49 +0200

On Sat, Jun 21, 2003 at 03:45:44PM +0200, Thorsten Horstmann wrote:

Hallo,

> Meine Loesung der d):
> zuerst wird nach der Laenge des Wortes unterschieden. Wenn |w|=2n+1
> gilt, dann ist w auf jeden Fall in der Sprache.
> Bei |w|=2n ist etwas schwieriger. Aus w = w_1w_2...w_nw_(n+1)...w_(2n)
> folgt das es ein i geben muss (1<=i<=n) so dass w_i != w_(i+n) gilt.
> Dieses muss der Automat (mit Hilfe von viel nicht-Determinismus) suchen.

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:

w = w_1 ... w_k ... w_n

Als w_i wird zB w_1 ausgewählt. Jetzt kann ich aber nicht mehr wissen
ob das w_k das erste Symbol der 2. Hälfte ist oder nicht.

Falls i so speichere, daß i von der nichdetermistisch
angenommenen Mitte k Symbole entfernt ist und damit das
Symbol, mit dem verglichen wird k Symbole vom Ende
entfernt ist kann folgendes passieren:

w_1 ... w_{2n-3} w_{2n-2} w_{2n-1} w_{2n}

Als erstes Symbol wird zB w_{2n-3} gewählt. Die Mitte wird zwischen
w_{2n-2} und w_{2n-1} gelegt, so daß dann w_{2n-3} mit w_{2n-1}
verglichen wird, was aber nicht notwendigerweise relevant sein muß.

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

Bye, Lutz
-- 
signature intentionally left blank


Other related posts: