DM517: Computability (5 ECTS)

STADS: 15011201

Level
Bachelor course

Teaching period
The course is offered in the autumn semester.
1st quarter.

Teacher responsible
Email: jbj@imada.sdu.dk

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

Comment:
Ubegrænset deltagerantal. Kurset kører i 1. kvartal.

Prerequisites:
None

Academic preconditions:
The topics from Algorithms and Data structures 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
After the course the students are expected to be able to:

• Construct finite automata and regular expressions for simple languages
• Construct pushdown automata and context-free grammars for simple languages
• Apply theorems and alogorithms for regular and context-free languages within the scope of the course´s syllabus
• Prove that certain languages are not regular or context-free using e.g. closure properties and pumping lemmas
• Construct deterministic and non-deterministic Turing machines that decide a given language or compute a given function
• Prove the undecidability of certain languages using Rice´s theorem and reductions


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:
(a) Madatory assigments, pass/fail, internal evaluation by teacher. The assignments must be passed in order to take the written exam.
(b) 4 hour written exam, 7-point grading scale, external examiner.

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
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.