Exam in Programmes as Data

BSWU BPRD IT University, E2015

Skriftlig eksamen, Programmer som Data

7.–8. januar 2016

Dette eksamenssæt har 7 sider. Tjek med det samme at du har alle siderne.

Eksamenssættet udleveres elektronisk fra kursets hjemmeside torsdag 7. januar 2016 kl 09:00.

Besvarelsen skal afleveres elektronisk i LearnIt senest fredag 8. januar 2016 kl 14:00 som følger:

_ Besvarelsen skal uploades på kursets hjemmeside i LearnIt under Submit Exam Assignment.

_ Der kan uploades en fil, som skal have en af følgende typer: .txt, .pdf eller .doc. Hvis du for eksempel

laver besvarelsen i LATEX, så generer en pdf-fil. Hvis du laver en tegning i hånden, så scan den og inkluder

det skannede billede i det dokument du afleverer.

Der er 4 opgaver. For at få fulde point skal du besvare alle opgaverne tilfredsstillende.

Hvis der er uklarheder, inkonsistenser eller tilsyneladende fejl i denne opgavetekst, så skal du i din besvarelse

beskrive disse og beskrive hvilken tolkning af opgaveteksten du har anvendt ved besvarelsen. Hvis du mener det er

nødvendigt at kontakte opgavestiller, så send en email til sap@itu.dk med forklaring og angivelse af problem

i opgaveteksten.

Din besvarelse skal laves af dig og kun dig, og det gælder både programkode, lexer- og parserspecifikationer,

eksempler, osv., og den forklarende tekst der besvarer opgavespørgsmålene. Det er altså ikke tilladt at lave

gruppearbejde om eksamen.

Din besvarelse skal indeholde følgende erklæring:

Jeg erklærer hermed at jeg selv har lavet hele denne eksamensbesvarelse uden hjælp fra andre.

Du må bruge alle bøger, forelæsningsnoter, forelæsningsplancher, opgavesæt, dine egne opgavebesvarelser,

internetressourcer, lommeregnere, computere, og så videre.

Du må naturligvis ikke plagiere fra andre kilder i din besvarelse, altså forsøge at tage kredit for arbejde, som

ikke er dit eget. Din besvarelse må ikke indeholde tekst, programkode, figurer, tabeller eller lignende som er skabt

af andre end dig selv, med mindre der er fyldestgørende kildeangivelse, dvs. at du beskriver oprindelsen af den

pågældende tekst (eller lignende) på en komplet og retvisende måde. Det gælder også hvis den inkluderede kopi

ikke er identisk, men tilpasset fra tekst eller programkode fra lærebøger eller fra andre kilder.

Hvis en opgave kræver at du definerer en bestemt funktion, så må du gerne definere alle de hjælpefunktioner

du vil, men du skal definere den ønskede funktion så den har netop den type og giver det resultat som opgaven

kræver.

Udformning af besvarelsen

Besvarelsen skal bestå af forklarende tekst (på dansk eller engelsk) der besvarer spørgsmålene, med væsentlige

programfragmenter indsat i den forklarende tekst, eller vedlagt i bilag (der klart angiver hvilke kodestumper der

hører til hvilke opgaver).

Vær omhyggelig med at programfragmenterne beholder det korrekte layout når de indsættes i den løbende

tekst, for F#-kode er som bekendt layoutsensitiv.

Snydtjek

Til denne eksamen anvendes Snydtjek. Det betyder at cirka 20% vil blive udtrukket af studeadministrationen i

løbet af eksamen. Navne på disse personer vil blive offentliggjort på kursets hjemmeside fredag den 8. januar

klokken 14:00. Disse personer skal stille i lokale 2A18 fredag den 8. januar klokken 15.00, dvs. kort tid efter

deadline for aflevering i learnIt.

Til Snydtjek er processen, at hver enkelt kommer ind i 5 minutter, hvor der stilles nogle korte spørgsmål

omkring den netop afleverede besvarelse. Formålet er udelukkende at sikre at den afleverede løsning er udfærdiget

af den person, som har uploaded løsningen. Du skal huske dit studiekort.

Vi forventer hele processen kan gøres på lidt over 1 time.

Det er obligatorisk at møde op til snydtjek i tilfælde af at du er udtrukket. Udeblivelse medfører at

eksamensbesvarelsen ikke er gyldig og kurset ikke bestået. Er man ikke udtrukket skal man ikke møde op.

1

BSWU BPRD IT University, E2015

Opgave 1 (25 %): Regulære udtryk og automater

Betragt dette regulære udtryk over alfabetet fk; l; v; h; sg:

k(l|v|h)+s

Ved antagelse, at

k svarer til kør

l svarer til ligeud

v svarer til venstre

h svarer til højre

s svarer til slut

så beskriver det regulære udtryk strenge, der symboliserer køreture, eksempelvis turen fra hjem til ITU.

1. Giv nogle eksempler på strenge der genkendes af dette regulære udtryk. Giv en uformel beskrivelse af

sproget (mængden af alle strenge) der beskrives af dette regulære udtryk.

2. Konstruer og tegn en ikke-deterministisk endelig automat (“nondeterministic finite automaton”, NFA) der

svarer til det regulære udtryk. Husk at angive starttilstand og accepttilstand(e). Du skal enten bruge en systematisk

konstruktion svarende til den i forelæsningen eller som i Introduction to Compiler Design (ICD),

eller Basics of Compiler Design (BCD), eller forklare hvorfor den resulterende automat er korrekt.

3. Konstruer og tegn en deterministisk endelig automat (“deterministic finite automaton”, DFA) der svarer til

det regulære udtryk. Husk at angive starttilstand og accepttilstand(e). Du skal enten bruge en systematisk

konstruktion svarende til den i forelæsningen eller som i Introduction to Compiler Design (ICD), eller Basics

of Compiler Design (BCD), eller forklare hvorfor den resulterende automat er korrekt.

4. Betragt nedenstående uendelige mængde af strenge over alfabetet fl; v; hg. For at blive i analogien med

køreture kan du antage at l svarer til ligeud, v for venstre og h for højre. For eksempel vil strengen vll