Mål:
Kursen skall ge en introduktion till formella språk och automatateori.
Förkunskaper:
TATM 43 Grundläggande diskret matematik.
Organisation:
Föreläsningarna tar upp teoretiska avsnitt och på lektionerna övas dessa med problem.
Kursinnehåll:
Ändliga automater och reguljära uttryck.
Kontextfria grammatikor och pushdown-automater.
Chomskys språkhierarki.
Orientering om Turingmaskiner och oavgörbarhetsproblem.
Kurslitteratur:
"Introduction to Automata Theory, Languages and Computation" av John Hopcraft, Jeffrey Ullman (Addison&Wesley 1979).
Examination:
UPG 1 Obligatoriska inlämningsuppgifter.
TEN 1 En skriftlig tentamen.