# 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:**- 16 lectures: lecture 1-6 + lecture 14/15 (Victor) are replaced by prerecorded videos, lecture notes, and resource sessions in Teams. Lecture 7-13 + 16 (Jonas) are replaced by lecture notes and resource sessions in Teams.
- 9 tutorial sessions (replaced by resource sessions in Teams, and e-mail correspondence with
**Jonas**).

**Digital platforms:**- Course web page: general information about the course.
- Microsoft Teams: used for resource sessions, replacing tutorials/lectures.
- Lisam: only for managing hand-ins (homework and the exam).

**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 take-home 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.)*) - A "compendium" with tutorial exercises.

Page responsible: Victor Lagerkvist

Last updated: 2021-03-19- Michael Sipser,