TILDA, ÖVNING 5  4 okt 2007 (Linda lånar Mikas grupp igen)

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.

______________________________________________________________________   
**********************************************************************
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. ORD AV TYPEN bbabbabbbaabbb
   a) Skriv ett reguljärt uttryck för ord i alfabetet {ab} som
      innehåller ett jämnt antal a.
   c) Skriv en syntax för sådana ord.
   d) Skriv ett program som kollar att ord följer syntaxen.

______________________________________________________________________   
**********************************************************************
4. Syntax för kanadensare
   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


______________________________________________________________________   
======================================================================
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 ORD AV TYPEN bbabbabbbaabbb

a) b*(ab*ab*)*

b) <ord>      ::= <b*><(ab*ab*)*>
   <b*>       ::= <nothing> | b <b*>
   <(ab*ab*)*>::= <nothing> | a <b*> a <b*> <(ab*ab*)*>


c)
   from queue import Queue
   q = Queue()
   for tkn in raw_input("Skriv ett ord:"):
       q.put(tkn)
   
   def readord():
     readbstar()
     readrest()
   
   def readbstar():
     if q.isempty(): 
        return
     if q.peek() == "b":
       q.get()
       readbstar()
   
   def readrest():
     if q.isempty(): 
        return
     reada()                    
     readbstar()
     reada()
     readbstar()
     readrest()
   


   def reada():
     if q.isempty(): 
        raise Exception, "a saknas"
     if q.get() != "a": 
        raise Exception, "a saknas"      
   
   try:                                  
     readord()                                 
     print "Följer syntaxen!"      
   except Exception,msg:                            
     print msg,"före",
     while not q.isempty():
       print q.get(),
     print

______________________________________________________________________   
======================================================================
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>"