TDDA 89 FORMELLA SPRÅK OCH AUTOMATATEORI, 3,5 poäng

/Formal Languages and Automata Theory/
För C1, D3, DX3, D4
Utbildningsområde: Teknik
Ämnesgrupp: Datalogi
Fördjupningsnivå: B
Klassning för datavetenskaplig examen: Datavetenskap, datalogi.

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.