Automata and Computability

5 ECTS credits
150 h study time

Offer 2 with catalog number 2019971BNR for all students in the 2nd semester at a (B) Bachelor - advanced level.

Semester

2nd semester

Enrollment based on exam contract

Impossible

Grading method

Grading (scale from 0 to 20)

Can retake in second session

Yes

Enrollment Requirements

Enrolling in ‘Automata and Computability’ means that you simultaneously follow 'Structure of Computer Programs 1' or 'Higher-Order Programming' or have successfully passed ‘Structure of Computer Programs 1’ or 'Higher-Order Programming'.

Taught in

Dutch

Faculty

Faculteit Wetenschappen en Bio-ingenieurswetensch.

Department

Computer Science

Educational team

Ann Nowe (course titular)
Joost Vennekens

Activities and contact hours

26 contact hours Lecture
26 contact hours Seminar, Exercises or Practicals
50 contact hours Independent or External Form of Study

Course Content

1. Syntax (formal languages):

1.1. Regular languages and finite automata: equivalence, (non)determinism, optimization.
1.2. Context free grammars: definitions and general properties (e.g. normalforms), pushdown automata.
1.3. Context-sensitive grammars: definitions and general properties, linear bounded automota
1.4. Introduction to parsing.

2. Computability: Solvable and unsolvable problems, Theorem of Church, Turing Machines.

3. Computability with respect to Formal Languages.

Course material

Digital course material (Required) : Automaten en berekenbaarheid, Kopieën van de transparanten van de titularis, Leerplatform
Handbook (Required) : An Introduction to Formal Languages and Automata, Peter Linz, 6de, Jones & Bartlett Learning, 9781284231601, 2017

Additional info

Copies of the slides, summaries of the courses and detailed proofs are available on Canvas.
Warning: the slides and/or summaries are not sufficient material to pass the exam; the handbook is mandatory.

Handbook: Linz: 'An Introduction to Formal Languages and Automata,Jones & Bartlett Learning, 2017.

Additional material:

Inleiding in de theorie van de formele talen,V.J. Rayward-Smith
Berekenbaarheid,V.J. Rayward Smith

Learning Outcomes

General competencies

Knowledge:
The student knows the basic concepts introduced in this course (such as: regular language, context-free language, finite automaton, Turing machine, context-sensitive grammar, ...) and can define them.

Insight:
The student can reason about the possibilities and restrictions of formal languages (regular languages, contextfree languages, context-sensitive languages, ... ) and their corresponding automata.
The student can explain the basic concepts of this course.
The student can reconstruct proofs and explain details of them orally.

The use of knowledge and insight:
The student can apply the theorems and techniques on unseen languages/automata/grammars.

Judgement ability:
The student can judge where in the Chomsky hierarchy a formal language resides and argue correctness of this answer.
The student can judge whether some previously unseen problem is (semi-)decidable or (semi-)computable.
The student can identify mistakes in a given mathematical proof.

Creation:
The student can can create correct mathematical proofs voor variants of a known theorem.
The student can create an automoaton/grammar that accepts a given formal language.

Grading

The final grade is composed based on the following categories:
Oral Exam determines 50% of the final mark.
Written Exam determines 50% of the final mark.

Within the Oral Exam category, the following assignments need to be completed:

Oral exam theory with a relative weight of 1 which comprises 50% of the final mark.

Note: The exam is a closed book exam. To obtain a passing grade, a student must score well on two basic questions. The additional questions have a higher degree of difficulty and determine the grade.

Within the Written Exam category, the following assignments need to be completed:

Written exam exercises with a relative weight of 1 which comprises 50% of the final mark.

Note: There is a mandatory written exercise exam. This exam is also a closed book.

Additional info regarding evaluation

50% exercises
50% theory

Theory: There is a mandatory closed book oral exam. To pass the exam the student should score well on two or three basic questions. The additional question will make up the final degree.

Exercises: There is a mandatory closed book written exam.

Both exams are organised in the second semester

Allowed unsatisfactory mark

The supplementary Teaching and Examination Regulations of your faculty stipulate whether an allowed unsatisfactory mark for this programme unit is permitted.

Academic context