| TDDD14 |
Formella språk och automatateori, 6 hp
/Formal Languages and Automata Theory/
För:
D
I
Ii
IT
MMAT
|
| |
Prel. schemalagd
tid: 50
Rek. självstudietid: 110
|
| |
Utbildningsområde: Teknik
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:
- Hantera reguljära och kontextfria språk; konstruera, förstå och tillämpa deras formella definitioner.
- Beskriva relationer mellan språk och språkklasser.
- Tillämpa grundläggande parsningstekniker.
- Förklara skillnaden mellan avgörbara och oavgörbara problem.
|
| |
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: |
TEN1
UPG1
|
En skriftlig tentamen (U,3,4,5)
Inlämningsuppgifter (U,G)
|
5 hp
1 hp
|
| |
|
|