| TDDA89 |
Formella språk och automatateori, 3,5 p
/Formal Languages and Automata Theory/ |
||
Prel. schemalagd
tid: 50 |
|||
|
Utbildningsområde: Teknik Ämnesgrupp: Datalogi, Datateknik Nivå (A-D):B |
|||
| Datavetenskap Datavetenskap, datalogi. |
|||
|
Mål:
Kursen skall ge en introduktion till formella språk och automatateori. |
|||
| Förkunskaper: (gäller studerande antagna till program som kursen ges inom, se 'För:' ovan) TATA35 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 TDDB44 Kompilatorkonstruktion, TDDB41 Komplexitetsteori, TDDB40 Omskrivningssystem, TDDA43 Programmeringsteori, TDDB08 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, utges av institutionen för datavetenskap. |
|||
| Examination: | |||
| TEN1 UPG1 |
En skriftlig tentamen (U,3,4,5) Inlämningsuppgifter (U,G) |
3,5 p 0 p |
|
Undervisningsspråk är Engelska.
Institution: IDA.
Studierektor: sas-sr@ida.liu.se
Examinator: Wlodek Drabent
Länk till kurshemsida på kursgivande institution
Ansvarig utbildningsnämnd: UND
Engelsk kursplan
Om inget annat anges ovan gäller betygsskala enligt avsnitt a8.5 i de gemensamma bestämmelserna.
Kursplanen gäller för 2006 enligt beslut av ansvarig utbildningsnämnd.
 |
||||||
| ||||||