Department of Computer and Information Science |
Division of Software and Systems (SaS)
| Department of Computer and Information Science |
Division of Software and Systems (SaS)
|
News
[2008]The course got new code - TDDD14, and a new home page.
[2007-05-01]Home Assignment 2 posted.
[2007-04-27]The first half of Home Assignment 2 posted.
[2007-04-19]The slides on the pumping lemma for reg. lang. that were presented at the tutorial can be found here .
[2007-04-18]As announced at the tutorials, the deadline for the home assignment 1 has been postponed until 24th of April.
[2007-03-28]Complete home assignment 1 available.
[2007-03-21]The first problem of Home Assignment 1 posted.
[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.
- The course page in "Studiehandboken" (in Swedish, in English).
- The course page at IDA.
- List of contents of the course, explains the correspondence between the course and the book.
- Suggested reading before lectures: more detailed correspondence between the lectures and the textbook and other materials.
- Errata for the books.
- Slides used at the lectures.
- Latest exams: May 2007 [pdf], August 2006 [pdf], June 2006 [pdf], January 2006 ([pdf]), August 2005 ([pdf]), May 2005 ([pdf]), May 2003 ([pdf], [ps.gz]), June 2002 ([pdf] [ps.gz]), June 2000, January 2000. The exams in other file formats and older exams available here.
- Some example solutions of exam problems.
- A summary of differences between the old and current textbook.
Organization
Schedule.Lectures, planned content:
- Overview and introduction
- Deterministic finite automata
- Nondeterministic finite automata
- Finite automata with epsilon-transitions
Regular expressions- Myhill-Nerode theorem, minimization of finite automata
- Properties of regular languages
- Context-free grammars
- Simplification of context-free grammars, normal forms
- Pushdown-automata
- Context-free grammars and pushdown-automata
- Properties of context-free languages
- LL(1)-grammars (if there is time); LR(0)-grammars
- LR(1)-grammars
- Turing machines
- Undecidability
- The Chomsky hierarchy; summary of the course
Tutorials:
Tutorials are basically problem solving sessions. This schedule may be modified according to needs.
- Basic concepts
- Finite automata
- Regular expressions and minimization of finite automata
- Properties of regular languages
- Discussion/feedback on the first set of assignments
Context-free grammars- Pushdown automata
Properties of context-free languages- LR-grammars
- Turing machines
- Discussion/feedback on the second set of assignments
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]
