TDDD85 |
Formella språk och automatateori, 6 hp
/Formal Languages and Automata Theory/
För:
U
|
|
Prel. schemalagd
tid: 50
Rek. självstudietid: 110
|
|
Utbildningsområde: Teknik
Huvudområde: Datateknik, Datavetenskap Nivå (G1,G2,A): G1
|
|
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) i nästan varje gren av datalogin. Efter att ha fullgjort kursen skall studenten kunna:
- Hantera reguljära och kontextfria språk; förklara och analysera deras beskrivningar.
- Beskriva relationer mellan språk och språkklasser.
- Tillämpa grundläggande parsningstekniker.
- Förklara Turingmaskiner.
|
|
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 sprÃ¥k och pushdown-automater. Deterministiska kontextfria sprÃ¥k, LR parsning. Chomskys sprÃ¥khierarki. Orientering om Turingmaskiner.
|
|
Kurslitteratur: D. C. Kozen, Automata and Computability, 1997, Springer Verlag.
Kompendium, publiceras på webben.
|
|
Examination: |
TEN1
UPG2
|
En skriftlig tentamen (U,3,4,5) Inlämningsuppgifter (U,G) |
5 hp 1 hp
|
|
|
|