Ändliga automater och formella språk

Kursen är obligatorisk inom Datavetenskap, kandidatprogram (N1COS).

Kursen kan ingå i följande program:

1. Computer Science, masterprogram (N2COS)
2. Matematiska vetenskaper, masterprogram (N2MAT)
3. Matematikprogrammet (N1MAT)

Kursen ges även som fristående kurs vid Göteborgs Universitet.

För att vara behörig till kursen ska studenten ha avklarat 45 hp inom datavetenskap eller matematik, inklusive följande kurser:

• 7,5 hp i diskret matematik (till exempel DIT984, MMG200 eller motsvarande)
• 7,5 hp i programmering (till exempel DIT441, DIT143, DIT013, DIT948, DIT953, MVG200 eller motsvarande)

Följande kunskapsnivå i Engelska krävs: Engelska 6/Engelska nivå 2 eller motsvarande från ett erkänt internationellt test, t.ex. TOEFL, IELTS.

Kursen handlar huvudsakligen om ändliga automater, reguljära uttryck och kontextfria grammatiker. Den innehåller också en kort introduktion till Turingmaskiner.

Ändliga automater och reguljära uttryck är enkla beräkningsmodeller. De används bland annat
för lexikalanalys, mönsterigenkänning, och styrning av trafiksignaler. Vidare kan deras teori illustrera grundläggande begrepp inom mängdlära och läran om diskreta strukturer.

Kontextfria grammatiker används för att parsa och analysera både konstgjorda språk (till exempel programmeringsspråk) och naturliga språk. Turingmaskiner ger en mer uttrycksfull beräkningsmodell. De hjälper dataloger att förstå begränsningarna hos mekaniska beräkningar genom att ge en precis definition av algoritmbegreppet.

Innehåll i lite mer detalj: Bevis. Ändliga automater, reguljära uttryck och relateradebalgoritmer. Kontextfria grammatiker. Egenskaper hos reguljära och kontextfria språk. Kort introduktion till Turingmaskiner.

Efter godkänd kurs ska studenten kunna:

Kunskap och förståelse

• Definiera olika begrepp inom automatteori och teorin om formella språk, som (icke-) deterministisk automat, reguljärt uttryck, reguljärt språk, kontextfri grammatik, kontextfritt språk samt Turingmaskin.

Färdigheter och förmåga

• Bevisa egenskaper hos (vissa) språk, grammatiker och automater med rigorösa matematiska metoder.
• Utforma ändliga automater, reguljära uttryck och kontextfria grammatiker som accepterar eller genererar vissa språk.
• Beskriva språket som accepteras av en ändlig automat eller som genereras av ett reguljärt uttryck eller en kontextfri grammatik.
• Transformera beskrivningar av reguljära språk mellan följande formalismer: deterministiska och ickedeterministiska ändliga automater samt reguljära uttryck.
• Förenkla automater och kontextfria grammatiker.
• Avgöra om ett ord hör till ett visst (reguljärt eller kontextfritt) språk.
• Utforma Turingmaskiner för enkla uppgifter.

Värderingsförmåga och förhållningssätt

• Manipulera formella beskrivningar av (vissa) språk, grammatiker och automater.

Föreläsningar, övningar.

Undervisningsspråk: engelska

Kursen examineras genom inlämningsuppgifter och en individuell skriftlig salstentamen.

Om en student som har underkänts två gånger på samma examinerande moment önskar byta examinator inför nästa examinationstillfälle ska en sådan begäran bifallas om det inte finns särskilda skäl däremot (6 kap. 22 § HF).

Om en student har fått besked om pedagogiskt stöd från Göteborgs universitet med rekommendation om anpassad examination och/eller anpassad examinationsform kan examinator, i det fall det är förenligt med kursens lärandemål och förutsatt att inte orimliga resurser krävs, besluta att bevilja studenten anpassad examination och/eller anpassad examinationsform.

Om en kurs har avvecklats eller genomgått en större förändring ska studenten erbjudas minst två examinationstillfällen, utöver ordinarie examinationstillfälle. Dessa tillfällen fördelas under en tid av minst ett år, dock som längst två år efter det att kursen avvecklats/förändrats. Vad gäller praktik och verksamhetsförlagd utbildning (VFU) gäller motsvarande, men med begränsning till endast ett ytterligare examinationstillfälle.

Om en student har fått besked om att denne uppfyller kraven för att vara student vid Riksidrottsuniversitetet (RIU-student) har examinator rätt att besluta om anpassning vid examination, om detta görs i enlighet med Lokala regler gällande RIU-studenter vid Göteborgs universitet

Delkurser

1. Skriftlig salstentamen, 4,5 hp
   Betygsskala: Mycket väl godkänd (5), Väl godkänd (4), Godkänd (3) och Underkänd (U)
2. Inlämningsuppgifter, 3 hp
   Betygsskala: Godkänd (G) och Underkänd (U)

På kursen ges något av betygen Mycket väl godkänd (5), Väl godkänd (4), Godkänd (3) och Underkänd (U).

För att få något av betygen 5, 4 eller 3 krävs dels att man får betyget G på delkursen inlämningsuppgifter, och dels att man får godkänt resultat (5, 4 eller 3) på delkursen skriftlig salstentamen. I så fall är betyget på hela kursen betyget på delkursen skriftlig salstentamen. I annat fall är betyget på hela kursen U (underkänt).

Kursen utvärderas genom möten, både under och efter kursen, mellan lärare och studentrepresentanter. Ett anonymt skriftligt frågeformulär skickas även ut till studenterna efter kursens slut. Resultaten av utvärderingarna används för att förbättra kursinnehållet och som indikation till vilka delar som skulle kunna läggas till, tas bort, förbättras eller ändras.

Kursen är samläst med Chalmers.

Kursen ersätter kursen DIT322, 7,5 hp. Den här kursen kan inte ingå i en examen som innehåller DIT322. Den kan inte heller ingå i en examen som bygger på en annan examen där DIT322 ingår.