Hemtal 6

A) 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?

Ton	Sannolikhet
A	0.2
B	0.06
C	0.3
D	0.04
E	0.1
F	0.1
G	0.2

B) Komprimering

Läs en introduktion till komprimering och se hur Huffmankodning och Lempel-Ziv fungerar.

1. Vad är redundans (redundancy)?

2. Vi komprimerar en fil på 400 MB och då krymper den till 100 MB. Vad är komprimeringsgraden i procent?

3. Vad innebär förlustfri komprimering?

4. Rita upp ett Huffmanträd för tabellen till höger, och skriv upp huffmankoderna.
   Huffmankoda sedan BAGGABAGGAFGC

5. Vad är algoritmen för Lempel-Ziv?

---

Hemtalet tas med till övningen 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, samt antal poäng.