Overordnede kursusmål
De studerende lærer at forstå og anvende de centrale modeller der
bliver introduceret i løbet af kurset og at bruge software
værktøjer relateret til disse formalismer.
Læringsmål
En studerende, der fuldt ud har opfyldt kursets mål, vil kunne:
- anføre forskelle i udtrykskraft af de præsenterede formelle
modeller
- tolke betydningen af en given beskrivelse i en formel model
(f.eks. automater, grammatiker, semantikker)
- udlede en beskrivelse i en formel model (f.eks. automater,
grammatiker, semantikker) for en ønsket egenskab eller opførsel
givet som en tekstuel beskrivelse
- oversætte til en anden model (f.eks. regulære udtryk til
NFA)
- ændre en given beskrivelse svarende til et givet kriterie
(f.eks. minimering af automater, fjernelse af ubrugelige
produktioner, tilføjelse af sprogkonstruktioner)
- anvende udvalgte værktøjer relateret til de formelle modeller
(f.eks. lexere, parsere)
- afgøre om en beskrivelse i en formel model opfylder en givet
egenskab
- udlede egenskaber ved at anvende bevisstrategier (f.eks.
strukturel induktion, givne sætninger)
- vælge formelle modeller der kan være nødvendige eller nyttige
ved løsning af et givent problem
- opnå målene som del af en gruppe, mens det individuelle ansvar
opretholdes
- kommunikere sine konstruktioner og løsninger på en klar og
præcis måde
Kursusindhold
Kurset omfatter tre emner:
(1) Regulære sprog og deres sammehæng med endelige automater,
praktiske anvendelser (fx søgning, leksikalsk analyse,
sikkerhedsautomater) og nogle væsentlige teoretiske resultater
(herunder lukketheds- og afgørlighedsegenskaber).
(2) Kontekstfri sprog og deres anvendelser (til parsing af
programmer, dokumenter og formatteret data) sammen med en kort
indføring til stakautomater og deres sammenhæng med kontekstri
sprog.
(3) Formelle metoder og deres brug til både modellering og analyse
af IT systemers egenskaber.
Kurset involverer praktisk brug af forskellige værktøjer og de
studerende skal løse både teoretiske og praktiske opgaver.
Litteraturhenvisninger
- Introduction to Automata Theory, Languages, and Computation, John
E. Hopcroft, Rajeev Motwani, Jefrey D. Ullman, (Second or) Third
Edition, Addison-Wesley, 2007.
- Semantics With Applications - An Appetizer, Hanne Riis Nielson
and Flemming Nielson, Springer 2007.
- Formal Semantics - An Appetizer, Flemming Nelson and Hanne Riis
Nielson, manuscript.
Bemærkninger
Kurset gives på engelsk.
Sidst opdateret
28. juni, 2017
