# 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'' Pascal programs (accepted by a certain compiler).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:**

17 lectures (including one guest lecture)

9 tutorial sessions**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:**- Dexter C. Kozen,
*Automata and Computability*, 1997, ISBN 0-387-94907-0, Springer Verlag.*(Offical course book)* - Michael Sipser,
*Introduction to the Theory of Computation*3rd edition, 2013, Cengage Learning. ISBN13: 978-1-133-18781-3.*(Recommended course book)* - A "compendium" with tutorial exercises.
- A chapter on LR parsing (will be distributed separately).

Page responsible: Jonas Wallgren

Last updated: 2018-04-13- Dexter C. Kozen,