| TDDD14 |
Formella språk och automatateori, 4 p
/
6 hp
/Formal Languages and Automata Theory/ |
||
Prel. schemalagd
tid: 50 |
|||
|
Utbildningsområde: Teknik Ämnesgrupp: Datateknik Nivå (A-D):B Huvudområde: Datateknik, Datavetenskap Nivå (G1,G2,A): G2 |
|||
| Datavetenskap Datavetenskap, datalogi. |
|||
|
Mål:
IUAE-matris
Kursen skall ge en introduktion till formella språk och automatateori. Automater och formella språk uppträder (eventuellt i olika förklädnader) inästan varje gren av datalogin. Efter att ha fullgjort kursen skall studenten kunna:
|
|||
| Förkunskaper: (gäller studerande antagna till program som kursen ges inom, se 'För:' ovan) Grundläggande matematik, t.ex. en kurs i diskret matematik OBS! Tillträdeskrav för icke programstudenter omfattar vanligen också tillträdeskrav för programmet och ev. tröskelkrav för progression inom programmet, eller motsvarande. |
|||
| Påbyggnadskurser Kompilatorkonstruktion, Komplexitetsteori, Programmeringsteori, Logik fördjupningskurs |
|||
| Organisation: Föreläsningarna tar upp teoretiska avsnitt och på lektionerna övas dessa med problem. |
|||
| Kursinnehåll: �"ndliga automater och reguljära uttryck. Kontextfria grammatiker och pushdown-automater. Deterministiska kontextfria språk, LR parsning, Chomskys språkhierarki. Orientering om Turingmaskiner och oavgörbarhetsproblem. |
|||
| Kurslitteratur: D. C. Kozen, Automata and Computability, 1997, Springer Verlag. Kompendium, publiceras på webben. |
|||
| Examination: | |||
|
TEN3
UPG3
|
En skriftlig tentamen (U,3,4,5) Obligatorisk laborationsuppgift (U,G) |
5 hp 1 hp |
|
Undervisningsspråk är Engelska.
Institution: IDA.
Studierektor: Tommy Färnqvist
Examinator: Ulf Nilsson
Länk till kurshemsida på kursgivande institution
Ansvarig programnämnd: Data&Medie
Engelsk kursplan
 |
||||||
| ||||||