Weekly notes and further information concerning the course DM517 Fall 2011

Reeksamen 23 Januar 2012

Det vil være 30 minuters mundtlig eksamen uden forberedelse. Eksaminationen tager udgangspunkt i det trunkne spørgsmål fra listen nedenfor. Efter ca 20 minutter stilles generelle spørgsmål i pensum. Der vil primært blive testet forståelse af emnerne, samt evne til at anvende teorien (f.eks pumpelemmaer).

Endelige automater og regulære udtryk.
Kontekstfrie sprog og stakautomater.
Pumpelemmaer og lukningsegenskaber for regulære og kontekstfrie sprog.
Turing maskiner (herunder modeller og ækvivalens af disse).
Uafgørlighed (specielt halting problemet).

The course starts on August 29

You should check the schedule on the faculty pages.

The book is Michael Sipser, Introduction to the theory of computation, Thompson 2006. You should buy the book before the first lecture!

You can find a list of misprints in the book here

Notes on undecidability proofs

These notes which you can find here are in Danish as they are a rewrite of notes from a precursor of this course.

Weekly notes

Smartboard "slides" from lectures

Previous exam problems in DM17 in danish

Note that DM17 was a larger course so some of the questions do not reflect the pensum for DM517. Still many of the problems directly reflect the kind of problems you may meet at the exam. If you do not read danish, please ask a fellow student to help translate the few danish words in the problems.

Previous exam problems in DM17 in Danish and English

Recent exams in DM517 (from 2009-2010 the course was given by Thomas Sejr Jensen)

Last modified: Fri Dec 16 09:35:06 CET 2011

Joergen Bang-Jensen (jbj@imada.sdu.dk)