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.
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].
