Hemtal 5

A) Automater och textsökning

• Rita upp en KMP-automat för att söka efter ordet KAKAOKAKA i en text.
• Ange också next-vektorn för automaten.
• Kan automater användas till annat än textsökning? Ge två exempel!
• Vad är komplexiteten för KMP-sökning? Tala om vad variablerna innebär!
• Hur fungerar Rabin-Karps algoritm för textsökning?
• Skriv ett reguljärt uttryck som matchar ditt efternamn stavat på olika sätt.

B) Syntax

• Skriv en syntax för chokladkakor av typen
  CHILI, RUSSIN, NÖT & MANDELCHOKLAD
  Raden avslutas med CHOKLAD och det kan ingå valfritt antal
  smaksättare, även bara en:
  MINTCHOKLAD
  eller ingen:
  CHOKLAD
• Visa med de tre exemplen ovan att din syntax fungerar.
• Skriv också upp ett exempel som inte följer syntaxen.
• Vad är rekursiv medåkning?

C) Minne

• Hur mycket minne har du på din mobil/iphone/mp3-spelare?
• Hur många låtar/foton/filmer får du plats med?
• Öppna ett terminalfönster på en av Ubuntu-datorerna och ta reda på hur mycket minne du har där. (Tips: fs lq)
• Hur stor är den största filen du lagrat där? (Tips: ls -sl)