Navigation auf


Department of Informatics Artificial Intelligence Lab (ARCHIVE)

Formal Methods for Computer Science II

Module: BINF2100
Type: Lecture with Exercises
ECTS: 6 points
Lecture: Friday, 08:30-12:00
Venue: BIN 2.A.01
Lecturers: Prof. Rolf Pfeifer, Dr. Rudolf Füchslin
Target audience: BSc/3+
Precondition: Assessment RO 2004 passed, at least provisional
Language: English
Assessment: Exercises & written exam. Exam date: Friday, 10.01.2014, 8:00 - 10:00
Assistants: Qian Zhao, Konstantinos Dermitzakis, Tobias Klauser


  • 09.01.2014: The final exam will take place tomorrow Friday, 10 January 2014, from 08:00 to 10:00 am in BIN 0.K.02. The exam starts at 8:00 sharp! So be there a couple of minutes in advance. The only things you are allowed to take with you are a pen, your student ID card and a dictionary.
  • 20.12.2013: The solution sheet for exercise 5 and the final list with exercise points have been uploaded. If you want to fetch your exercise corrections, please send an e-mail to Tobias.
  • 13.12.2013: The slides for lecture 13 on Morphological Computing have been uploaded.
  • 06.12.2013: The solution sheet for exercise 4 and the updated list with exercise points have been uploaded.
  • 02.12.2013: The slides of Helmut Hauser's lecture on Reservoir Computing are now online.
  • 29.11.2013: Exercise 5 and the links to the demos shown in today's class have been added to the website. An errata for the lecture script has also been added.
  • 28.11.2013: The slides for Graphs & Network II and II have been uploaded.
  • 22.11.2013: The solution for exercise 3 are online. There is now also a List with exercise points up to exercise 3.
  • 20.11.2013: The slides on Fuzzy Logic (lecture 9) and Fractals/L-Systems (lecture 10) have been uploaded.
  • 08.11.2013: The slides for lecture 8 and exercise sheet 4 are online.
  • 01.11.2013: Please note that the lecture schedule was slightly changed. As a consequence, the hand out/in dates for exercise 5 were moved forward by one week.
  • 01.11.2013: Slides for lecture 7 are online.
  • 31.10.2013: The solution sheet, an example solution for the programming task and accompanying correction notes for exercise 2 have been uploaded. Exercise 2 will be handed out and discussed on 1 November 2013.
  • 25.10.2013: Exercise 3 and corresponding materials have been uploaded.
  • 18.10.2013: The solution to exercise 1 is online.
  • 17.10.2013: The slides for lecture 5 & 6 are online.
  • 10.10.2013: Exercise 2 and the materials for the Python tutorial are online.
  • 09.10.2013: The slides for lecture 4 are online.
  • 04.10.2013: The slides for lecture 3 and for the ANTLR demo are online.
  • 27.09.2013: The slides for lecture 2 and exercise 1 are online.
  • 20.09.2013: The corrected slides for lecture 1 are online.
  • 09.09.2013: Lecture script is online.
  • 03.09.2013: Tentative schedule and lecture information is online.

Final Examination and Exercises

  • During the semester, there will be 5 exercise sheets, with a total of 100 (normalized) points.
  • You are allowed to do the exercises in pairs. If you choose to do them in pairs, you are required to submit only one answer sheet per pair, stating clearly each student's name on the answer sheet.
  • In order to be eligible for the final exam, you need to achieve at least 50% of the points from the exercises.
  • The final exam will take place on Friday, 10 January 2014, from 08:00 to 10:00 am in BIN 0.K.02. The exam starts at 8:00 sharp! So be there a couple of minutes in advance. The only things you are allowed to take with you are a pen and a dictionary.
  • Below you can download a list with the current exercise points (currently up to and including exercise 4). If you don't find yourself on the list or spot any error, please send an e-mail to Tobias.


Date Topic Hand out Hand in
20 September Introduction, Formal Languages I
27 September Formal Languages II
4 October Automata Theory I
11 October Automata Theory II Exercise 1
18 October Logic I
25 October Logic II Exercise 2
1 November Cellular automata
8 November Dynamical systems / Markov models / Hidden Markov models Exercise 3
15 November Fuzzy logic and other kinds of logics
22 November Fractals / Reservoir computing
29 November Graphs & Networks I Exercise 4
6 December Graphs & Networks II
13 December Morphological computation / Alternative models of computation Exercise 5
20 December Wrap-up / Final discussion


The following list contains corrections for errors that where discovered in the lecture script. If you encounter additional errors, please send an e-mail to Tobias.

Page 3-16 In example 3.7, there is a semicolon (;) missing after the number rule.
Page 4-3 In formula for the elements of the transition matrix the indices for column and row are switched. The correct formula should read pij = P(Xn = i | Xn-1 = j) instead of pij = P(Xn = j | Xn-1 = i).
Page 4-11 The numbers for (R,S) and (S,S) in the lower right box are wrong. The correct values are (R,S) 0.0063 and (S,S) 0.0648.
Page 8-16 The entries for the commands + and - are switched in Table 8.1. The correct actions are: + turn left and - turn right
Page 9-7 The formula for the maximum number of edges mmax should read mmax = n(n-1) for a directed graph (a), and mmax = ½ n(n-1) for an undirected graph (b).


Suggested books and articles

All books are available as Handapparat in the IFI library. Look for "Prof. Pfeifer Handapparat". Study the books in the library or copy the relevant parts.

Automata theory and languages:

  • J. E. Hopcroft, R. Motwani and J. D. Ullmann (2003), Introduction to Automata Theory, Languages, and Computation, 2nd Edition
  • T.A. Sudkamp (1991), Languages and Machines - An Introduction to the Theory of Computer Science

Logic, models of computation:

  • Papadimitriou (1995), Computational complexity, Addison Wesley
  • Rechenberg and Pomberger (2002), Informatik-Handbuch, 3. Auflage

Recursion, fractals and chaos:

  • Flake (1998), The Computational Beauty of Nature, MIT Press

Graphs and networks:

Weiterführende Informationen


Teaser text