Kursen består av flera delar med gemensam kärna i automater och verktyg för formella språk. Kursen inleds med studier kring ändliga automater och reguljära språk samt stackautomater och kontextfria språk. Kursen fortsätter med översättarteknik där lexikal, syntaktisk och semantisk analys ingår. Verktyg som YACC och Lex introduceras i laborationsmomentet där en kompilator konstrueras för ett enkelt programspråk. En mellankod genereras som i en senare fas kan översättas till exekverbar kod. Kursen avslutas med studier kring beräkningsbarhet och komplexitet. Turingmaskiner diskuteras och olika klasser av komplexitet behandlas.
Kursen består av tre moment:
Moment 1, Formella språk och ändliga automater, 3 hp där FSR 1, 6 och 7 behandlas.
Moment 2, Parsning i Yacc och Lex, 3 hp där FSR 8 behandlas.
Moment 3, Berökningsbarhet och komplexitet, 1.5 hp där FSR 2-5 behandlas.
Förväntade studieresultat
Kunskap och förståelse Efter avslutad kurs ska studenten kunna
Återge och exemplifiera pumping-lemman för reguljära och kontextfria språk. (FSR1)
Diskutera Church-Turing tesen samt begreppen avgörbarhet och beräkningsbarhet. (FSR2)
Diskutera haltproblemet och dess oavgörbarhet samt kunna återge och exemplifiera Rice teorem. (FSR3)
Definiera och förklara klasserna P och NP. (FSR4)
Definiera begreppen polynomtidsreduktion och NP-komplett förklara vad som är syftena med dessa. (FSR5)
Färdighet och förmåga Efter avslutad kurs ska studenten kunna
Definiera, skapa och tolka olika representationer av reguljära och kontextfria språk samt översätta mellan dem. (FSR6)
Tillämpa syntaxstyrd översättning på enklare kontextfria grammatiker. (FSR7)
Använda verktyg för lexikal- och syntaxanalys för att skapa en parser. (FSR8)
Behörighetskrav
För tillträde till kursen krävs minst 15hp kurser i datavetenskap varav en kurs i Datastrukturer och algoritmer baserat på programspråket C, (5DV127/5DV149) eller motsvarande kunskaper.
Undervisningens upplägg
Undervisningen bedrivs i form av föreläsningar, arbete i datorlabb och övningar i mindre grupper. Utöver schemalagda aktiviteter krävs även individuellt arbete med materialet.
Examination
Examinationen på Moment 1 (Formella språk och ändliga automater), Moment 2 (Parsning i Yacc och Lex) och Moment 3 (Beräkningsbarhet och komplexitet) sker genom ett antal obligatoriska uppgifter. På momenten ges något av betygen Underkänd (U) eller Godkänd (G).
Examinationen på kursen som helhet sker genom obligatoriska inlämningsuppgifter i de tre momenten samt en frivillig skriftlig tentamen för högre betyg. För betyget Godkänd (G) på kursen krävs att samtliga moment 1-3 är godkända. På den skriftliga tentamen sätts något av betygen Underkänd (U), Godkänd (G), eller Väl godkänd (VG). Vid genomförd och godkänd skriftlig tentamen blir betyget för hela kursen det som erhållits på tentamen.
Studerande som godkänts i ett prov får inte undergå förnyat prov för att få ett högre betyg. I detta fall innebär det att studenten kan skriva den frivilliga skriftliga tentamen maximalt en gång.
För studerande som inte godkänns vid ordinarie provtillfälle anordnas ytterligare provtillfälle. En student som utan godkänt resultat har genomgått två prov för en kurs eller en del av en kurs, har rätt att få en annan examinator utsedd, om inte särskilda skäl talar emot det (HF 6 kap. 22 §). Begäran om ny examinator ställs till prefekten vid Institutionen för datavetenskap.
Övriga föreskrifter
TILLGODORÄKNANDE I en examen får denna kurs ej ingå, helt eller delvis, samtidigt med en annan kurs med likartat innehåll. Vid tveksamheter bör den studerande rådfråga studievägledare vid Institutionen för datavetenskap och/eller programansvarig för sitt program.
Tillgodoräknande av studier prövas individuellt (se http://www.umu.se/utbildning/antagning/tillgodoraknande/).
Litteratur
Litteraturlistan är inte tillgänglig via den webbaserade utbildningskatalogen.
Kontakta aktuell institution.
