Übung 3: Lookup-Table

lkbaerenfaenger
Mausschubser
Mausschubser
Beiträge: 44
Registriert: 13. Mär 2012 12:44

Übung 3: Lookup-Table

Beitrag von lkbaerenfaenger »

Hallo,

im Rahmen von Übung 3 müssen wir ja auch eine Lookup-Table für das vorgegebene Beispiel anfertigen. Ich habe mir zuächst - wie in den 2013er-Videos - einen Automaten gezeichnet und davon die Lookup-Table abgeleitet. Interessehalber habe ich dann versucht den Algorithmus zu verstehen, der im Algo-Wiki für die Erstellung der Lookup-Table verantwortlich ist (Induction basis -> Implementation -> Steps 3 - 4). Hierzu habe ich 2 Fragen:

:arrow: 1) In der Lookup-Table, die ich von meinem Automaten abgeleitet habe, hat [3,m] den Wert 1, was meiner Meinung nach richtig sein müsste. Wenn ich allerdings mithilfe der o.g. Schritte 3 - 4 der Induktionsbasis diesen Wert der Tabelle berechne, erhalte ich 0 als Ergebnis. Was ist nun richtig?

:arrow: 2) Schritt 4.2 aus dem Wiki lautet wir folgt: "While k > 0 and (T[1], ..., T[k]) != (T[j-k+2], ..., T[j], c), decrease k by 1." Im Folgenden versuche ich die besagte Position [3,m] der Lookup-Table zu berechnen.

Code: Alles auswählen

j = 3 and c = "m"
4.1. Set k := min(m, j+ 1) = min(4, 4) = 4
4.2.1. k=4, (T[1], ..., T[4]) != (T[3-4+2], ..., T[3], "m"), da "meme" != "memm"
4.2.2. k=3, (T[1], ..., T[3]) != (T[3-3+2], ..., T[3], "m"), da "mem" != "emm"
4.2.3. k=2, (T[1], ..., T[2]) != (T[3-2+2], ..., T[3], "m"), da "me" != "mm"
4.3.4. k=1, (T[1], ..., T[1]) ?? (T[3-1+2], ..., T[3], "m"), ...
Zu was für einem Wort löst sich der rechte Teil der letzten Zeile (T[4], ..., T[3], "m") auf. Instinktiv würde ich sagen "emm". Dann würde aber gelten "m" != "emm" und wir müssen k=0 setzen. Dann wäre [3,m]=k=0, was mit meinem Automaten (wie in 1) geschildert) nicht übereintstimmt. Man könnte natürlich (T[4], ..., T[3]) als Illegal Expression abtun und sich auf das "m" beschränken, dann würde gelten "m" == "m", k=1 würde nicht weiter verringert werden und deshalb würde ebenfalls gelten [3,m]=k=1, was sich mit meinem Automaten decken würde. Was ist nun richtig?

Über eine Hilfestellung würde ich mich sehr freuen.

LG Lucas

Schnell
Nichts ist wie es scheint
Beiträge: 23
Registriert: 11. Feb 2010 22:27

Re: Übung 3: Lookup-Table

Beitrag von Schnell »

Hi,
schau dir mal die vorlesung vom 26.4.2012 an. Ganz am Anfang wurde dein Problem erläutert und es ist in der Tat so, dass wenn der rechte Index größer als der Linke ist es dann einfach 0 ist. In dem Fall hättest du also m=m. bei k=1

lkbaerenfaenger
Mausschubser
Mausschubser
Beiträge: 44
Registriert: 13. Mär 2012 12:44

Re: Übung 3: Lookup-Table

Beitrag von lkbaerenfaenger »

Ich danke Dir :!:

Antworten

Zurück zu „Archiv“