TILDA, ÖVNING 5

Automater, reguljära uttryck, syntax

______________________________________________________________________   
**********************************************************************
1. ABRAKADABRA
Konstruera en KMP-automat som söker efter texten "ABRAKADABRA"
Ange även den next-vektor som definierar automaten.

Ungefär hur många jämförelser behövs för att automaten ska se 
att ordet inte finns med i "Harry Potter och Fenixorden", en 
bok på 1.8 Mbyte?
______________________________________________________________________   
**********************************************************************
2. Värstingvrålsautomat (Tildatenta 31 augusti 2000)
Skriv en KMP-automat som söker efter OHOJ-OHOJ! i en texfil 
med nedtecknade värstingvrål från en vitmaktskonsert.
Ange också den next-vektor som definerar automaten.

______________________________________________________________________   
**********************************************************************
3. 
a) Givet det reguljära uttrycket
     s(a|o)nd-?låda
   Skriv upp tre strängar som matchas av det reguljära uttrycket
   och ett som inte gör det.
   
b) Söka efter Kronskog
   Skriv ett reguljärt uttryck som matchar alla tänkbara sätt att 
   stava namnet Kronskog (Crounskog, Krohnskoog, etc).

______________________________________________________________________   
**********************************************************************
4. Syntax för kanadensare (Tildatenta 13 mars 2004)
   Olle sitter och rättar ett tentatal. Tentatalet går ut på att 
   man ska skriva en grammatik för meddelanden av följande typ:
   
   Kanot 42, kanot 666, kanot 4711 och kanot 17 ska in!
   Kanot 1 och kanot 2 ska in!
   Kanot 13 ska in!
   
   Vilken eller vilka av följande fyra alternativ kan producera 
   dessa meddelanden? Motivera med exempel varför de övriga inte 
   kan producera dem.
   En del av alternativen kan producera oönskade meningar, man 
   vill tex inte ha 'Kanot 1 och kanot 2, kanot 3 och kanot 4 
   ska in!' 
   Vilket eller vilka av alternativen kan producera oönskade 
   meningar? Ge exempel.
   
(1)  <meddelande> ::= Kanot <tal><svans> | 
                      <meddelande> kanot <tal><svans>
     <svans> ::= och| ska in! | ,
     <tal> ::= 1 | 2 | 3 | ...
      
(2)  <meddelande> ::= Kanot <tal> ska in! | 
                      Kanot <tal><svans>
     <svans> ::= och kanot <tal> ska in! |
                  , kanot <tal><svans>
     <tal> ::= 1 | 2 | 3 | ...
      
(3)  <meddelande> ::= Kanot <tal><svans>
     <svans> ::= ska in! | , kanot <tal> | 
                 och kanot <tal>
     <tal> ::= <svans> | 1 | 2 | 3 | ...
      
(4)  <meddelande> ::= Kanot <tal><svans> | 
                      kanot <tal><svans>
     <svans> ::= ska in! | , | och
     <tal> ::= 1 | 2 | 3 | ...
   
   
______________________________________________________________________   
**********************************************************************
5. Värsta webbsyntaxen (Tildatenta 31 augusti 2000)
   
En webbfil innehåller dels webbsidans text, dels taggar 
för radbrytningar och indragningar. Taggen <BR> ger ny 
rad och för att få indragning av ett textavsnitt skriver 
man taggen <Q> före och taggen </Q> efter. Exempelvis 
ger webbfilen 

      Organismer <BR> <Q> Djur
      <BR> <Q> Flugor <BR>
      Sillar <BR> </Q> Svamp
      <BR> <Q> Flugsvamp <BR>
      Sillkremla <BR> </Q> </Q>

följande webbsideutseende: 

      Organismer
         Djur
            Flugor
            Sillar
         Svamp
            Flugsvamp
            Sillkremla

Skriv en syntax för webbfiler där endast dessa taggar och 
vanlig text förekommer. Du kan få använda <text> för att 
beteckna godtycklig taggfri text. 


LÖSNINGAR

______________________________________________________________________   
======================================================================
1.          A  B  R  A  K  A  D  A  B  R  A


        i   1  2  3  4  5  6  7  8  9  10 11
   next(i)  0  1  1  0  2  0  2  0  1  1  0


  KMP-sökning tar n+m jämförelser, där m är antal tecken i 
  söksträngen och n är antal tecken i texten. 
  Alltså 1.8 miljoner+11.
______________________________________________________________________   
======================================================================
2.          O  H  O  J  -  O  H  O  J  !


        i   1  2  3  4  5  6  7  8  9  10
   next(i)  0  1  0  2  1  0  1  0  2  5

______________________________________________________________________   
======================================================================
3. a)  sandlåda, sand-låda, sondlåda men inte syndlåda
   b)  [CK]rou?h?nskoo?g [CK]ro[uh]*nskoo?g

______________________________________________________________________   
======================================================================
4. Syntax för kanadensare

Alternativ 1 och 2 kan producera alla meningarna.
Alternativ 3 och fyra kan inte producera 
     'Kanot 1 och kanot 2 ska in!'

Alternativ 1 och 4 godkänner felaktigt 'Kanot 4 och'.
Alternativ 3 godkänner felaktigt 'Kanot och kanot 2'.

______________________________________________________________________   
======================================================================
5. Värsta webbsyntaxen

<webbfil> ::= <nothing> 
              | <text> 
              | <Q><webbfil></Q> 
              | <webbfil><BR><webbfil>
<Q>       ::= "<Q>"
</Q>      ::= "</Q>"
<BR>      ::= "<BR>"