[AlgEnComp] Vragen bij Hfst 5 van Algo

[Beatle]

Vraag 1:
Op p83 staat een pseudo-code. Maar ik geraak niet in alle termen wijs uit. zo een Qi met een Unie teken. Iets te chinees. Kan er iemand de tappen in het nederlands uitleggen.

Vraag 2:
Op p89 staat er een stelling waar staat dat het algoritme bepaalt woordt in 0(l+n). Hoe komt men aan die n?

Grtz

[Quintus Maximus]

Vraag1: Qi zijn alle mogelijke staten die ge kunt tot geraken vanuit alle staten in Qi-1 als je ai inleest.
dus Qi = { d(q,ai) | q in Qi-1 }

Om dit compleet te maken moet het der nog de epsilon sluiting aan toevoegen wat je in het volgende deel doet.

Vraag2:
x = a1...an
y = b1...bl
we zoeken de eerste occurence van y in x.
Bepaal de falingsfunctie:
algoritme van O(l)
dan moet met die falingsfunctie in constante tijd de automaat gevormd worden die (p87) ten hoogste 2n stappen doet>
Dus in totaal O(l + n)