DD3372 Automater och språk 6,0 hp

Automata and Languages

  • Utbildningsnivå

    Forskarnivå
  • Huvudområde

  • Betygsskala

    P, F

Det finns inget planerat kurstillfälle.

Lärandemål

Det övergripande målet med kursen är att ge doktoranderna ett djupt förståelse för beräkning och effektiv beräkningsbarhet genom abstrakta begreppet av automater och språken som de känner igen. Samtidigt kommer doktoranderna att få bekanta sig med de viktiga begreppen tillstånd, icke-determinism och minimering.

Kursens huvudsakliga innehåll

Kursen går igenom ändliga automater, stack-automater och Turingmaskiner, och de viktiga relaterade språkklasserna av de regulära och kontextfria språk. Relationen mellan automater och språk fastställs med hjälp av olika transformationer. Språkklasserna karakteriseras med några klassiska satser som Myhill-Nerodes teorem och Chomsky-Schützenbergers teorem.

Behörighet

Kurser motsvarande SF1630 Diskret matematik och DD1350 Logik för dataloger.

Litteratur

Hopcroft, Motwani and Ullman
Introduction to Automata theory, Languages and Computation

Examination

  • EXA1 - Examination, 6,0, betygsskala: P, F

Krav för slutbetyg

Sex hemtal, två labbar och en skriftlig tenta.

Ges av

EECS/Teoretisk datalogi

Examinator

Dilian Gurov <dilian@kth.se>

Versionsinformation

Kursplan gäller från och med HT2014.
Examinationsinformation gäller från och med VT2019.