[informatik-bonn] Re: Aufgabe 1

  • From: Thorsten Horstmann <Thorsten.Horstmann@xxxxxx>
  • To: informatik-bonn@xxxxxxxxxxxxx
  • Date: Mon, 23 Jun 2003 15:12:35 +0200

Lutz Oberst wrote:

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).

Ja. Aber dann ist doch auch das i nicht mehr als Zahl verfügbar, da ich ja alle Symbole die ich beim Lesen bis i auf den Stak gelegt habe, bei Lesen bis 2i wieder runternehmen muß. Dann weißt du also nicht mehr wieviel Zeichen schon gelesen wurden, kannst also auch nicht überprüfen ob hinter dem fragelichen Partner noch 2i+j Zeichen kommen.

ich brauche i als Zahl ueberhaupt nicht. Das w_i ist das interessante. Nachdem ich 2i Zeichen gelesen habe ist der Keller leer, richtig. Hinter dem (zu ratenden) fragelichen Partner muessen noch n-i (nicht 2i+j sorry) Zeichen kommen, denn 2i+(n-i)+(n-i) = 2n = |w| Wenn also das j=n-i richtig geraten wurde, dann liegen gerade so viele Symbole wieder im Keller das man bis ans Ende vom Wort kommt.


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

Idee bei a) ist, daß sich das Komplement forgendermaßen darstellen läßt: { L^m U^n L^k | m!=n } \cup { L^k U^m L^n | m!=n } \cup \ { \epsilon }

hmmm... L^n U^n L^n U^n ist da aber z.B. nicht drin....


bei c): { L^m U^k L^n U^l | m!=n } \cup { L^k U^m L^l U^n | m!=n } \cup { \epsilon }

hier analog.


Irgendwie hab' ich das Gefuehl das man a) auf b) und c) auf d) abbilden
kann.... aber das klappt bisher nicht so richtig.

a) liegt im cvs unter ...info4/übungen/oberst/8/aufgaben.tex
und ist schlecht nachprüfbar, da es an mein erstes Asseblerprogramm
erinnert. Müsste aber evtl stimmen.

hab' keinen cvs-Zugang. (liegt dort auch was anderes als eure Loesungen?)

c) war mir zuviel gefrickel für 1 Punkt.

geht mir so langsam auch so....


Gruss,
  -Thorsten


Other related posts: