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 og XML
dokumenter) sammen med en kort indføring til stakautomater og deres
sammenhæng med kontekstri sprog.
(3) Transitionssystemer, deres brug i operationel semantik for
forskellige programmeringsparadigmer, samt formelle teknikker til
at sammenligne specifikationer.
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, Third Edition,
Addison-Wesley, 2007.
- Semantics With Applications - An Appetizer, Hanne Riis Nielson
and Flemming Nielson, Springer 2007.
Bemærkninger
Kurset gives på engelsk.
Sidst opdateret
28. oktober, 2016
