Eksamen
Formålet med kurset at den studerende skal kunne
- referere den basale terminologi (strenge, sprog, klasser af sprog, samt basale operationer på disse)
- beskrive basale abstrakte sprogformalismer (regulære udtryk, endelige automater, regulære grammatikker, kontekstfri grammatikker) - fra intuitivt niveau og konkrete eksempler til formel notation og generelle definitioner
- beskrive egenskaber ved formalismerne, bl.a. ækvivalens, begrænsninger og beslutningsprocedurer
- forklare og udføre algoritmer, der oversætter mellem formalismerne eller afgør beslutningsproblemer - fra konkrete eksempler til generelle og formelle beskrivelser
- bevise og analysere egenskaber ved formalismerne (ved hjælp af konstruktive beviser og induktionsbeviser) - fra intuitivt niveau til formelle detaljer.
Eksamen vil vurdere i hvor høj grad den studerende besidder disse kompetencer.
Pensum
Martin, kap. 1-4 (i kap. 4.5: kun Definition 4.29 og Theorem 4.30, uden beviser) og kap. 6 (dog ikke Theorem 6.7 s. 211-213 og Theorem 6.13 s. 216-218)
Desuden forventes kendskab forelæsnings-slides'ene og opgaverne på ugesedlerne.
Eksamensspørgsmål
- regulære udtryk
- endelige automater
- lukkethedsegenskaber
- nondeterministiske automater
- minimering af automater
- begrænsninger af regulære sprog
- kontekstfri grammatikker
Vi anbefaler, at du som studerende har forberedt en disposition, svarende til ca. 10-12 minutters præsentation, til hvert spørgsmål. Dvs. forbered en disposition til hvert spørgsmål inden eksamen. Afhængigt af ambitionsniveau kan du vælge hvad du helst vil snakke om indenfor hvert område og hvilken grad af formalitet du vil benytte. Dit eksamensspørgsmål bliver brugt som udgangpunktet for din eksamen, så brug det første minut på at skrive din disposition op på tavlen (kortfattet, i punktform). Læg derefter dine noter til side - vi skal nok stille spørgsmål og hjælpe, hvis du går i stå, eller hvis vi mener, at det vil være bedre for dig at gå lidt hurtigere frem.