TDDD14 Formal Languages and Automata Theory

Course information

Note! These course pages are currently being restructured. Please be patient.

• Objectives:
  This course will give an introduction to formal languages and automata theory. Automata and formal languages appear (possibly in various disguises) in almost every branch of computer science.

  A formal language is a set of strings where a string is a finite sequence of symbols. An example of a formal language is the set of all ``syntactically correct'' Python programs (accepted by a certain interpreter).

  A main problem that we will discuss is how to define an infinite language in a finite way. A related problem is to construct an algorithm that can decide whether a string is in the language or not. Both problems are of practical importance, for instance for constructing compilers and design of programming languages.

  At the end of the course we will introduce basics of the theory of computability. In particular we show that there exist uncomputable functions and that some tasks are unsolvable (i.e. no algorithm exists).

• Organisation:
  • 16 lectures.
  • 9 tutorials (lektioner).
• Examination:
  The examination consists of the following two parts. You must pass both to pass the course:
  • 2 sets of homework problems (UPG2)
  • A written examination (TEN1)
• Course literature:
  • Michael Sipser, Introduction to the Theory of Computation 3rd edition, 2013, Cengage Learning. ISBN13: 978-1-133-18781-3. (official course book)
    (Dexter C. Kozen, Automata and Computability, 1997, ISBN 0-387-94907-0, Springer Verlag. (Previous course book. May still be used if you already have it.))
  • Tutorial exercises.
  
  

  Page responsible: Victor Lagerkvist
  Last updated: 2024-03-21