ida logo Department of Computer and Information Science | Division of Software and Systems (SaS)

TDDA89 Formal Languages and Automata Theory


staff | resources | organization | literature | examination | goal | prerequisites |schedule
This page can be accessed as www.ida.liu.se/~TDDA89/ or www-und.ida.liu.se/~TDDA89/

News

news
[2008]

The course got new code - TDDD14, and a new home page.

news
[2007-05-01]

Home Assignment 2 posted.

news
[2007-04-27]

The first half of Home Assignment 2 posted.

news
[2007-04-19]

The slides on the pumping lemma for reg. lang. that were presented at the tutorial can be found here .

news
[2007-04-18]

As announced at the tutorials, the deadline for the home assignment 1 has been postponed until 24th of April.

news
[2007-03-28]

Complete home assignment 1 available.

news
[2007-03-21]

The first problem of Home Assignment 1 posted.

news
[2007-02-16]

In 2007 we run the course with only minor changes with respect to 2006.


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


Staff

Examiner: Włodek Drabent (email, office: Building B, Room 3D:446; telephone: 28 89 29)
Assistants: Jonas Wallgren (email, office: Building B, Room 3D:457; telephone 28 26 82)
Gustav Nordh (email, office: Building B, Room 3D:441; telephone 28 26 93)
Secretary: Gunilla Mellheden (email, office: Building B, Room B 329:216; telephone: 28 22 97)

Prerequisites

TATM43 Basic Discrete Mathematics, or TATM 90/TDDB 90 Discrete Mathematics and Logic.


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 (available at Linus & Linnea).

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 and style (less formal).
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.

Resources

Some of these resources may have restricted accessibility. In case of problems, open this page as www-und.ida.liu.se/~TDDA89/. You will be asked for your user id and password.

Organization

Schedule.

Lectures, planned content:

  1. Overview and introduction
  2. Deterministic finite automata
  3. Nondeterministic finite automata
  4. Finite automata with epsilon-transitions
    Regular expressions
  5. Myhill-Nerode theorem, minimization of finite automata
  6. Properties of regular languages
  7. Context-free grammars
  8. Simplification of context-free grammars, normal forms
  9. Pushdown-automata
  10. Context-free grammars and pushdown-automata
  11. Properties of context-free languages
  12. LL(1)-grammars (if there is time); LR(0)-grammars
  13. LR(1)-grammars
  14. Turing machines
  15. Undecidability
  16. The Chomsky hierarchy; summary of the course

Tutorials:

  1. Basic concepts
  2. Finite automata
  3. Regular expressions and minimization of finite automata
  4. Properties of regular languages
  5. Discussion/feedback on the first set of assignments
    Context-free grammars
  6. Pushdown automata
    Properties of context-free languages
  7. LR-grammars
  8. Turing machines
  9. Discussion/feedback on the second set of assignments
Tutorials are basically problem solving sessions. This schedule may be modified according to needs.

Examination

To complete the course the students are required to solve two sets of home assignments (see also the home assignment rules) and pass a written examination.

Home assignment deadlines: Wednesday week 16 (18/4) and Friday week 20 (18/5).

The written exams will be held on Thursday 2007-05-31 at 14-18, and on Saturday 2007-08-11 at 14-18. See here for further examination dates.

You receive 3.5 points (or 5.3 ECTS points) for the course.


[2007-05-29]