Del I. Ändliga automater och reguljära språk: determinering, modellprovning, 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.
Kursens övergripande syfte är att ge eleverna en djupgående förståelse för beräkning och effektiv beräkningsbarhet genom abstrakta begreppet av automater och språkklasserna de känner igen. Tillsammans med detta kommer studenterna att bekanta sig med de viktiga begreppen tillstånd, ickedeterminism och minimering.
Efter kursen kommer studenterna att kunna:
1) redogöra för huvudklasserna av automater och strukturella representationer (reguljära uttryck och grammatiker) och de motsvarande språkklasserna: konstruera en automat eller en grammatik från en informell språkbeskrivning [för betyg E].
2) relatera de olika klasserna med hjälp av språkbevarande transformationer; applicera transformationerna för att lösa konkreta problem: applicera transformationerna på konkreta exempel [E], definiera nya transformationer [C], visa att transformationerna är språkbevarande [A].
3) för varje språkklass förklara huvudkarakteriseringsteoremen; tillämpa teoremen för att lösa konkreta problem: förklara enklare teorem på konkreta exempel [E], förklara svårare teorem på konkreta exempel [C], tillämpa teoremen för att bevisa olika språkegenskaper [A].