Hemtal 5

A) Automater och textsökning

Läs om Finite-state machine, KMP, Boyer-Moore, Rabin-Karp och reguljära uttryck.

1. Rita upp en KMP-automat för att söka efter BADBALJA i en text. Ange även next-vektorn!

2. Vilken komplexitet har textsökning med KMP? Definiera alla variabler du använder.

3. Vilken komplexitet har textsökning med Boyer-Moore?

4. Vilken komplexitet har textsökning med Rabin-Karp?

5. Vad innebär tecknet * i ett reguljärt uttryck?

B) Syntax

Läs om kontextfi grammatik och rekursiv medåkning

1. Ge exempel på en omskrivningsregel utan rekursion...

2. ...och visa hur motsvarande funktion i en parser skulle kunna se ut.

3. Ge exempel på en omskrivningsregel med rekursion...

4. ...och visa hur motsvarande funktion i en parser skulle kunna se ut.

5. Vad har hänt när du får felmeddelandet SyntaxError: invalid syntax?

---

Hemtalet tas med till övning 5 (27 september) och rättas där!

Du som gjort uppgiften ska skriva ditt namn och personnummer överst till höger på alla blad.

Du som rättar ska skriva ditt namn och personnummer längst ner till vänster på första bladet.