Övning 6: Automater, reguljära uttryck (inför KS5) , syntax

​Mål:

  • Kunna rita upp en automat som en graf, och ange den som en övergångsmatris
  • Kunna konstruera en KMP-automat
  • Kunna beskriva hur textsökning med KMP, Rabin Karp och Boyer Moore fungerar,
  • känna till tidskomplexiteten för textsökning med dessa metoder,
  • och kunna avgöra för vilka fall respektive metod är lämplig
  • Kunna avgöra vilka strängar ett reguljärt uttryck matchar,
  •  samt formulera ett reguljärt uttryck som matchar givna strängar

Textsökning

  1. KMP-automat

    >>>Reglerna för hur next-vektorn bildas kan sammanfattas så här:

    • next[1]=0.
    • Annars är next[i]=1 om sökordet inte innehåller upprepningar.
    • ...men om de j senaste bokstäverna vi sett bildar början på sökordet sätts next[i]=j+1.
    • ...men om bokstav j+1 är samma som bokstav i sätts i stället next[i]=next[j+1].<<< Föreläsning 11

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

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

    Download lösning

  2. Reguljära uttryck

    a) Skriv ett reguljärt uttryck (regex) som letar upp alla namn i en text. Kan detta regex råka matcha även andra ord i texten?

    b) Skriv ett regex som matchar filnamnen på alla pythonfiler. När skulle man kunna behöva ett sådant regex?

    c) 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.

    d) Skriv ett reguljärt uttryck som matchar alla tänkbara sätt att stava namnet Kronskog (Crounskog, Krohnskoog, etc).

    Download lösning

  3. Automat på olika format

    Rita den graf som beskrivs av övergångsmatrisen
    "#" "%" "&" "?"
    1 2 1 1 1
    2 2 3 1 1
    3 2 1 4 1
    4 2 1 1 5
    lösning

  4. Rabin Karp

    På vilket sätt används en hashfunktion i textsökning med Rabin Karp? Visa med ett exempel.
    lösning

  5. Boyer Moore

    Vad är tidskomplexiteten för Boyer Moore? Berätta vad de ingående variablerna representerar, och förklara "bästa fallet".
    lösning

Mål:

  • skriva kod för en liten BNF-syntax (mindre än 10 regler) för ett formellt språk
  • systematiskt testa program för att upptäcka fel

Titta på Labb8, Labb9 och Labb10

Dessa tre labbar bygger på varandra.

I Labb 8 ska du skriva ett program som kan kontrollera enkla molekylformler, till exempel H2 eller C12. 

I Labb 9 ska du använda rekursiv medåkning för att kontrollera mer komplexa molekyler, t ex C6(H2O)6

I Labb 10 ska du bygga upp ett syntaxträd för molekylerna.

Det är viktigt att du strikt följer den givna syntaxen i dessa labbar, annars är det svårt att bli godkänd av domaren Kattis.

1. Övning till Labb 8

För varje regel ska du skriva en funktion (eller metod). När funktionen upptäcker brott mot regeln ska ett felmeddelande skickas. Vilken regel motsvarar vilket felmeddelande?

Saknad stor bokstav För litet tal 
<molekyl> ::= <atom> | <atom><num>
 
<atom> ::= <LETTER> | <LETTER><letter>
 
<LETTER>::= A | B | C | ... | Z
 
<letter>::= a | b | c | ... | z
 
<num> ::= 2 | 3 | 4 | ...

 

2. Övning till Labb 9

För varje regel ska du skriva en funktion (eller metod). När funktionen upptäcker brott mot regeln ska ett felmeddelande skickas. Vilken regel motsvarar vilket felmeddelande?

Saknad stor bokstav Saknad högerparentes För litet tal Okänd atom Felaktig gruppstart Saknad siffra 
<formel>::= <mol> \n
 
<mol> ::= <group> | <group><mol>
 
<group> ::= <atom> |<atom><num> | (<mol>) <num>
 
<atom> ::= <LETTER> | <LETTER><letter>
 
<LETTER>::= A | B | C | ... | Z
 
<letter>::= a | b | c | ... | z
 
<num> ::= 2 | 3 | 4 | ...

 

3. Övning till Labb 10

I labb 10 ska programmet rita upp en molekylstruktur som ett syntaxträd.

   Molekyl: Si(C3(COOH)2)4(H2O)7

molekylträd

Titta på syntaxen i labb 9, och rita med hjälp av den upp syntaxträd för följande molekyler:

  1. Molekyl:O
  2. Molekyl:CO2
  3. Molekyl:(CH3)2(CH2)4

4. Testning

Vad gör följande program?

import unittest

def kvadrat1(n):
 return n^2

def kvadrat2(n):
 return n**2

class Min_testklass(unittest.TestCase):
 
   def testa_kvadrat1(self):
      """Testar kvadrat med "^" """
      self.assertEqual(kvadrat1(5), 25)

   def testa_kvadrat2(self):
      """Testar kvadrat med "**" """
      self.assertEqual(kvadrat2(5), 25)

if __name__ == '__main__':
 unittest.main()


 

             

Syntax (gamla tentatal)

  1. 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 | ...
  2. 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 
          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 för att beteckna godtycklig taggfri text.

  3. Båtflytt (Tildatenta 6 april 2002)
    Under en seglingstävling vill varje båt hitta den snabbaste vägen till målet. Problemet är att en segelbåt inte kan segla hur som helst och att den seglar olika snabbt beroende på vindriktning och styrka. Antag att havet förenklat består av en massa jämnt fördelade punkter med information om vindstyrka, vindriktning och vilka punkter som finns runt om. Beskriv en algoritm som på ett så effektivt sätt som möjligt tar reda på vilka punkter som ligger utefter den snabbaste seglingsvägen givet en startpunkt och en slutpunkt. Båtägaren är orolig att hans miljövänliga bottenfärg ska nötas bort och vill därför istället ta d en väg som är kortast (dvs minst antal steg). Förklara vad som behöver ändras i din föregående algoritm.&#x0;

  4. SL-tentan 2015-03-20, uppgift 2 (betyg E)

    Rymdvarelserna är trehövdade och kommunicerar enbart med tre tecken ’+’,’O’,’=’ (ett per huvud) så deras skrifter blir ganska långa. För att textsöka i skrifterna föreslår tildastudenten algoritmen KMP. Visa hur en KMP-automat för följande sökta text ser ut och ange även next-vektorn. 
    + O = + O = = + O O O

  5. SL-tentan 2014-03-18, uppgift 8 (betyg C)

    Förtydligande: Skriv exempel på testfall som man kan testa syntaxen med. Se till att du får med olika sorters testfall.

  6. Värsta webbsyntaxen (Värstingtentan 31 augusti 2000, uppgift 6)

    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

          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ösning

     

    5. Syntax för kanadensare (Tildatenta 13 mars 2004, uppgift 8 (betyg C)) 

    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 | ...

    lösning

  7. Testfall (SL-tentan 2014-03-18, uppgift 8)

    Anta att du har skrivit en syntax för kommunikation mellan lokförare och trafikledning. Beskriv två olika sorters testfall som man kan testa syntaxen med.

    Tilläggsuppgift: Skriv exempel på testfall som man kan testa syntaxen med. Se till att du får med olika sorters testfall.

    lösning

    8. Syntaxträd

    Skriv en BNF-grammatik för vanliga taluttryck med operationerna + - * /. Den vanliga prioritetsordningen (* och / går före + och -) ska gälla mellan operatorerna. Man ska också kunna använda parenteser i taluttrycken.

    Rita till sist upp ett syntaxträd för uttrycket 2*(3+4*5).

    lösning