TILDA, ÖVNING 6 Automater, reguljära uttryck, komprimering Observera att finita automater inte ingår i kursen! **************************************************************** FRÅGOR 1. ABRAKADABRA Konstruera en KMP-automat som söker efter texten "ABRAKADABRA" Ange även den next-vektor som definierar automaten. 2. 000831: Värstingvrålsautomat 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. Reguljära uttryck * a* matchar noll eller flera a:n * a+ matchar ett eller flera a:n * a? matchar ett eller inget a * . matchar alla tecken utom radslut * [a-zA-Z] matchar alla engelska bokstäver * [abc] matchar a, b eller c * [^abc] matchar vilket tecken som helst utom a, b eller c * | betyder eller * man kan använda parenteser som man tror, tex [abz]=(a|b|c) 3. Använd alfabetet {a,b,c}. Skriv ett reguljärt uttryck och rita en finit automat för språket av ... a) alla ord med bara en bokstav. b) alla ord som innehåller delsträngen abc c) alla ord som har ett a före ett b före ett c d) alla ord som har åtminstonde ett a, ett b och ett c e) alla ord utom aa och aaa 4. ORD AV TYPEN bbabbabbbaabbb a) Skriv ett reguljärt uttryck för ord i alfabetet {ab} som innehåller ett jämnt antal a. b) Rita en ändlig automat som känner igen sådana ord. c) Skriv en syntax för sådana ord. d) Skriv ett program som kollar att ord följer syntaxen. 5. Smittskydd (Tildatenta 030828) Du har fått ett mail som innehåller tips mot spridning av virus. Informationen är komprimerad med ett Huffmanträd där nollor motsvarar vänster och ettor motsvarar höger (se figur, T kodas t.ex. som 11) Vad står det i meddelandet 010101011000110011001111 ? o / \ / \ / \ / \ o \ / \ o / \ / \ o o o T / \ / \ / \ D V H N Ä A 6. "man är mans gamman" kan man läsa i Havamal. Konstruera en huffmankod för tecknen i detta uttryck (rita trädet) och skriv sedan upp det i kodad form. **************************************************************** LÖSNINGAR 3. Några övningar på reguljära uttryck och finita automater a) (a+|b+|c+) b) (a|b|c)*abc(a|b|c)* Låt x=(a|b|c)* c) xaxbxcx d) x(ax(bxc|cxb)|bx(axc|cxa)|cx(axb|bxa))x e) a | (b|c)x | a(b|c)x | aa(b|c)x | aaa(a|b|c)+ 4 ORD AV TYPEN bbabbabbbaabbb a) b*(ab*ab*)* c) ::= <(ab*ab*)*> ::= | b <(ab*ab*)*>::= | a a <(ab*ab*)*> d) from queue import Queue q=Queue() for tkn in raw_input("Skriv ett ord:"): q.put(tkn) def readord(): readbstar() readpnyxtr() def readbstar(): if q.isempty(): return if q.peek()=="b": q.get() readbstar() def readpnyxtr(): if q.isempty(): return reada() readbstar() reada() readbstar() readpnyxtr() 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 6. "man är mans gamman" Totalt är det 18 tecken. Andelen av respektive tecken: Tecken | antal | andel ---------------------- m | 4 | 2/9 a | 4 | 2/9 n | 3 | 3/18 " " | 3 | 3/18 ä | 1 | 1/18 r | 1 | 1/18 s | 1 | 1/18 g | 1 | 1/18 Detta ger efter trädskapande till exempel följande huffmankoder: Tecken | Huffmankod ------------------- m | 10 a | 11 n | 010 " " | 011 ä | 0000 r | 0001 s | 0010 g | 0011 Vilket ger följande kodning av texten: 10 11 010 011 0000 0001 011 10 11 010 0010 011 0011 11 10 10 11 010