6 ECTS credits
150 h study time

Offer 2 with catalog number 1007146BNR 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
Students bachelor Engineering and students bachelor Mathematics and Data Science must have followed 'Higher-Order Programming', before they can enroll for 'Automata and Computability'. Students bachelor Computer Science must have followed 'Structure of Computer Programs 1', before they can enroll for 'Automata and Computability'.
Taught in
English
Faculty
Faculty of Sciences and Bioengineering Sciences
Department
Computer Science
Educational team
Antonio Paolillo (course titular)
Activities and contact hours
26 contact hours Lecture
26 contact hours Seminar, Exercises or Practicals
110 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 slides van de titularis, Leerplatform
Handbook (Required) : An Introduction to Formal Languages and Automata, Peter Linz, 6de, Jones & Bartlett Learning, 9781284077247, 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 competences


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:

  • Mondeling theorie examen with a relative weight of 1 which comprises 50% of the final mark.

    Note: Het examen is een gesloten boek examen. Om een voldoende te behalen moet een student goed scoren op een 2-tal basisvragen. De bijkomende vragen hebben een hogere moeilijkheidsgraad en bepalen de graad.

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

  • Schriftelijk oefeningen examen with a relative weight of 1 which comprises 50% of the final mark.

    Note: Er is een verplicht schriftelijk oefeningenexamen. Dit examen is ook geloten boek.

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

This offer is part of the following study plans:
Bachelor of Engineering: Electronics and Information Technology Profile Profile Computer Science (only offered in Dutch)
Bachelor of Engineering: verkort traject elektronica en informatietechnologie na vooropleiding industriële wetenschappen (only offered in Dutch)
Bachelor of Computer Science: Default track (only offered in Dutch)
Bachelor of Mathematics and Data Science: Standaard traject (only offered in Dutch)
Bachelor of Artificial Intelligence: Default track (only offered in Dutch)