# TDDD14 Formal Languages and Automata Theory

### Course information

### 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).

### Literature

#### Course Literature

- Dexter C. Kozen,
*Automata and Computability*, 1997, ISBN 0-387-94907-0, Springer Verlag.

- "Kompendium" with exercises and a chapter on LR parsing. (The chapter will be distributed separately.)

#### Additional Reading

- John E. Hopcroft and Jeffrey D. Ullman,
*Introduction to Automata Theory, Languages and Computation*, 1979, Addison-Wesley. The chapter on LR parsing mentioned above is from this book.

There is also 2nd revised edition (2001), by John E. Hopcroft, Rajeev Motwani and Jeffrey D. Ullman; it differs in scope (maybe more interesting and up-to-date) and style (less formal). The same comment applies to the 3rd edition (2007).

- Magnus Boman och Jussi Karlgren,
*Abstrakta maskiner och formella språk*, 1996, Studentlitteratur, Lund.

- Michael Sipser,
*Introduction to the Theory of Computation*, 1997, PWS Publishing Company; 2nd edition: 2005, Course Technology; 3rd edition 2012, Cengage Learning.

- Jeffrey Shallit,
*A Second Course in Formal Languages and Automata Theory*, Cambridge University Press, 2008. An interesting text on advanced subjects, many of them not mentioned in other books.

Page responsible: Jonas Wallgren

Last updated: 2013-09-07