Hoppa till huvudinnehållet

DD2373 Automater och språk 7,5 hp

Automater är matematiska maskiner, det vill säga abstrakta beräkningsapparater. Deras syfte är att fånga, studera och jämföra olika modeller och syn på det abstrakta begreppet beräkning och dess olika aspekter. Automaternas beräkningsstyrka kan karakteriseras genom språkklasserna (det vill säga mängderna av strängar över ett ändligt alfabet av symboler) som de kan känna igen. Viktiga begrepp inom datavetenskapen som tillstånd, ickedeterminism och minimering fångas med den enkla modellen av ändliga automater, som känner igen klassen av reguljära språk. Automater utgör grunden för implementeringen av många programmeringsspråk, varvid parsning ar en typisk tillämpning. En annan viktig orsak till att studera automater är att fånga upp begreppet effektiv beräkningsförmåga, det vill säga att karakterisera begreppet beräkning som en process som kan implementeras fysiskt. Detta gör att följande viktiga fråga kan ställas: vilka problem kan avgöras på ett algoritmiskt sätt och vad är gränserna för detta?

Välj termin och kursomgång

Välj termin och kursomgång för att se aktuell information och mer om kursen, såsom kursplan, studieperiod och anmälningsinformation.

Kursval

Gäller för kursomgång

VT 2024 automat24 programstuderande

Anmälningskod

61144

Rubriker med innehåll från kursplan DD2373 (VT 2024–) är markerade med en asterisk ( )

Innehåll och lärandemål

Kursinnehåll

Del I. Ändliga automater och reguljära språk: determinering, modellprövning, reguljära uttryck, tillståndsminimering, pumpningslemma, Myhill-Nerodes teorem, reguljär slutledning.

Del II. Stackautomater och kontextfria språk: kontextfria grammatiker och språk, parsning, Chomsky-Schützenbergers teorem, modellering av program med rekursion, pumpningslemma, stackautomater.

Del III. Turingmaskiner och effektiv beräkningsförmåga: Turingmaskiner, rekursiva mängder, universella Turingmaskiner, avgörbara och oavgörbara problem, Rices teorem, andra modeller för effektiv beräkning.

Lärandemål

Efter godkänd kurs ska studenten kunna

1) redogöra för huvudklasserna av automater och strukturella representationer (reguljära uttryck och grammatiker) och de motsvarande språkklasserna, samt konstruera en automat eller en grammatik från en informell språkbeskrivning

2) relatera de olika klasserna med hjälp av språkbevarande transformationer, tillämpa transformationerna för att lösa konkreta problem, samt tillämpa transformationerna på konkreta exempel 

3) för varje språkklass förklara huvudkarakteriseringsteoremen, tillämpa teoremen för att lösa konkreta problem, samt förklara enklare teorem på konkreta exempel.

För högre betyg ska studenten dessutom kunna

  • definiera nya språkbevarande transformationer [C] samt visa att transformationerna är språkbevarande [A]
  • för varje språkklass förklara svårare teorem på konkreta exempel [C] samt tillämpa teoremen för att bevisa olika språkegenskaper [A].

Kurslitteratur och förberedelser

Särskild behörighet

Kunskaper i algoritmisk komplexitet, 6 hp, motsvarande slutförd kurs DD2350/DD2352.

Kunskaper i diskret matematik, 6 hp, motsvarande slutförd kurs SF1688/SF1610/SF1630/SF1662/SF1679.

Gymnasiekursen Engelska B/6.

Rekommenderade förkunskaper

Ingen information tillagd

Utrustning

Ingen information tillagd

Kurslitteratur

Ingen information tillagd

Examination och slutförande

När kurs inte längre ges har student möjlighet att examineras under ytterligare två läsår.

Betygsskala

A, B, C, D, E, FX, F

Examination

  • HEM1 - Hemuppgifter, 2,5 hp, betygsskala: P, F
  • LAB1 - Laborationer, 2,5 hp, betygsskala: P, F
  • TEN1 - Hemtentamen, 2,5 hp, betygsskala: A, B, C, D, E, FX, F

Examinator beslutar, baserat på rekommendation från KTH:s handläggare av stöd till studenter med funktionsnedsättning, om eventuell anpassad examination för studenter med dokumenterad, varaktig funktionsnedsättning.

Examinator får medge annan examinationsform vid omexamination av enstaka studenter.

Möjlighet till komplettering

Ingen information tillagd

Möjlighet till plussning

Ingen information tillagd

Examinator

Etiskt förhållningssätt

  • Vid grupparbete har alla i gruppen ansvar för gruppens arbete.
  • Vid examination ska varje student ärligt redovisa hjälp som erhållits och källor som använts.
  • Vid muntlig examination ska varje student kunna redogöra för hela uppgiften och hela lösningen.

Ytterligare information

Kursrum i Canvas

Registrerade studenter hittar information för genomförande av kursen i kursrummet i Canvas. En länk till kursrummet finns under fliken Studier i Personliga menyn vid kursstart.

Ges av

Huvudområde

Datalogi och datateknik

Utbildningsnivå

Avancerad nivå

Påbyggnad

Ingen information tillagd

Övrig information

I denna kurs tillämpas EECS hederskodex, se:
http://www.kth.se/eecs/utbildning/hederskodex