DM517: Computability (5 ECTS)

STADS: 15001701

Level
Bachelor course

Teaching period
The course is offered in the autumn semester.
2nd quarter.

Teacher responsible
Email: thomas06@imada.sdu.dk

Timetable
Show entire timetable
Show personal time table for this course.

Comment:
Ubegrænset deltagerantal

Prerequisites:
None

Academic preconditions:
The topics from Algorithms and Datastructures should be known.

Course introduction
To introduce the theory of finite automata, formal language formalism and decidability of languages.

Qualifications
After taking the course the student is expected to be able to:

• describe a finite automaton accepting a given regular expression and conversely
• apply techniques such as closure properties and pumping lemmas for regular (context free) languages in order to demonstrate that a given language is not regular (context-free)
• give an account of those steps which are involved in proofs that a language is not regular (context-free) when one applies the corresponding pumping lemmas
• transform a given non-deterministic automaton into an equivalent deterministic finite automaton
• describe context free grammars and pushdown automatas for simple context-free languages and describe a pushdown automaton accepting an arbitrary context-free language, provided this is given by a context-free grammar
• describe Turing machines in words or using diagrams
• describe Turing machines deciding/accepting typical languages which are decidable respectively, Turing acceptable
• choosing, among the many different Turing machine models, one which is most suitable for a given decidable language and be able to argue for this choice
• give simple proofs for undecidability of languages and properties of languages for Turing machines
• apply Rice's theorem to prove undecidability of languages

Expected learning outcome


Subject overview
Finite automata, pushdown automata, Turing machines, regular languages, context-free languages, grammars, decidability

Literature

Meddeles ved kursets start.

Syllabus
See syllabus.

Website
This course uses e-learn (blackboard).

Prerequisites for participating in the exam
None

Assessment and marking:
4 hour written exam. External examiner. Danish 7 mark scale.

Reexam after 2nd quarter. The reexam is an oral exam with external examiner and grades according to the 7-point marking scale.

Expected working hours
The teaching method is based on three phase model.

Forelæsninger (22 timer) og eksaminatorier/laboratorier (20 timer).
Educational activities

Language
This course is taught in Danish or English, depending on the lecturer. However, if international students participate, the teaching language will always be English.

Course enrollment
See deadline of enrolment.

Tuition fees for single courses
See fees for single courses.