Finite Automata Theory and Formal Languages

TMV026/DIT321, LP4 2010


[ News | Prerequisites | Goals | Literature | Assignments | Schema | Exam | Course Evaluation | Contact Information | Useful Links ]


News

100901: Some time next week you should get the result of the exam. We will have revision of the exam ("granskning") on Tuesday 14th September at 12, room 6128 (6th floor od the EDIT building).

100830: Solutions to the exam on August 27th.

100611: Some time next week you should get the result of the exam. We will have revision of the exam ("granskning") on Monday 21st June at 10.30, room 6128 (6th floor od the EDIT building).

100609: You should have got an email from Börje Johansson with the link to the course evaluation questionnaire. Have a look into your spam box if you have not got the mail since many non-spam mails where filtered out lately. Please answer the questionnaire since your comments are very important for next year's course!

100527: Solutions to the exam on May 27th.

100527: Table with bonus points per person is available.

100525: Tomorrow (Wed. 26/5) after 10 you can fetch your last assignment from my office. I will not be there but the corrected paper assignment will be in a box on the floor in front of my door (room 6116 EDIT building).

100512: Extra class on Friday 21st 10-12 will take place in EL42.

100507: Here is the protocol from the meeting with students representative, written by the student.

100429: Please notice the corrected exericise 1 in assignment 4.

100427: For those interested in Haskell, here is a nicer version of the algorithm returning the equivalence classes. This version makes more use of Haskell primitive.

100421: New deadlines for the coming assignments, inclusive assignment 3. Check Schema.

100416: This is the solution to exercise Week 2, NFA 1 that Bassel wrote. Observe however that the intention of the exercise was not a formal proof as detailed by Bassel but more a justification based on the intuition one has on FA.

100415: On Friday 23rd at lunch time I will have a meeting with the student representative. Please see his contact information in the section on Course Evaluation and get in contact with him if you have any comments on the course.

100415: Observe that the web page of the book (linked from the section on Literature) contains solutions to some of the exercises in the book.

100413: Remember to put name and personal number when you submit an assignment. Otherwise we cannot keep proper track of the points.

100325: See the last paragraph in the Assignments section.

100324: There was an error om slide 24 of lecture 2: in general, concatenation does not distribute with intersection. Can you see why?
See the new slide 25 of lecture 2 for an explanation.

100318: Seems that the notion of binary tree (see assignment for week 1) is not as well known as I thought it was.
A binary tree (as in the assignment) is either a leave or a node with exactly 2 subtrees.

100317: Lectures have been moved out from EL42! Unfortunately, we will need to move around a bit each week. Check Time Edit for the new locations.
Observe that exercise classes are still on EL42. Experience show that far from everybody attend them (unfortunately). If needed, we will try to relocate them as well.

100316: Slides from lecture 2, exercises on DFA and NFA are now available.

100315: Slides from lecture 1, exercises and assignments for the first week now available.

[top]


Prerequisites

Knowledge in mathematics, including a course in Discrete mathematics, and in programming.

[top]


Goals

Finite automata are basic mathematical models of some physical systems. The theory of finite automata is fundamental in computer sciences. Besides having direct concrete applications, it is mathematically simple and elegant. It provides ideal illustrations of basic notions in mathematics (set theory, proof by induction).

The main applications in the text book (besides a mathematical model of a protocol) are about text search, lexical analysis and parsing. Other kind of applications (model of vending machines, traffic signals, etc...) require the notion of finite state transducers (Mealy machines), whose theory is almost identical to the one of finite automata.

[top]


Literature

Introduction to Automata Theory, Languages, and Computation, by Hopcroft, Motwani and Ullman. Addison-Wesley. Both second or third edition are fine for the course.

Observe that the web page of the book contains solutions to some of the exercises in the book.

Have a look also at Thierry Coquand's note on the two definitions for the transition function on strings (definition 2.2.4 in the book and the one we give in lecture 3) and why they are equivalent (exercises 2.2.2 and 2.2.3).

[top]


Assignments

There will be non-obligatory weekly assignments which will generate bonus points valid ONLY on the exams during 2010.

Each assignment will be of ca 10 pts. If a student has collected n pts in assignments, this will correspond to n/10 points in the exam. Exams are usually 60 points.

You should write your name and personal number when you submit an assignment, otherwise we cannot keep proper track of the points.

See below for deadlines.

OBS: Be aware that assignments are part of the examination of the course (since they give bonus points). Hence, they should be done individually! Standard procedure will be followed if copied solutions are detected.

[top]


Schema

Lectures: Tuesdays 10:00--11:45 and Thursdays 13:15--15:00 in EL42
Exercise sessions: Mondays 13:15--15:00 in EL42

See link at Time Edit for details.


Plan for the Lectures, Exercise Sessions and Assignments

Week Monday Tuesday Thursday Ass.Deadline Chapters Topics
1 -- 16 March 18 March   Ch. 1 Introduction. Proofs by (structural) induction. Alphabets and words.
2 22 March 23 March 25 March 25 March Ch. 2 -- 2.4 DFA and NFA. Equivalence between them.
3 12 April 13 April 15 April 15 April Ch 2.5. Ch. 3--3.2.2 and 3.4 NFA with epsilon-transitions. Regular expressions.
4 19 April 20 April 22 April 26 April Ch. 3.2.3. Ch. 4 -- 4.3 From RE to FA. Properties of Reg.Lang.
5 26 April 27 April 29 April 3 May Ch. 4.4. Ch. 5--5.2 Equivalence and Minimisation. Context-free grammars.
6 3 May 4 May 6 May 10 May Ch. 5.4. Ch. 7--7.2 Context-free grammars. Context-free languages.
7 10 May 11 May -- 18 May Ch. 7.3--7.4 (Ch. 9.4--9.5) Context-free languages.
8 17 May 18 May 20 May   Ch. 8 Turing machines. Exams.
9 -- -- 27 May     Exam

[top]


Exam

No books or written help during the exam.

Check the studieportalen for information about the exam.

[top]


Course Evaluation

GU student representative: Viktor Ljungström, mail: kontakt(at)viktorljungstrom(dot)se

On Friday 23rd at lunch time I will have a meeting with the student representative. Please get in contact with Viktor if you have any comments on the course.
Here is the protocol from the meeting with the student representative, written by the student.

[top]


Contact Information

Lecturer: Ana Bove, mail: bove(at)chalmers(dot)se
Assistant: Bassel Mannaa, mail: bassel(at)student(dot)chalmers(dot)se

Feel free to contact us if you have any further questions, either after the lectures/exercise sessions or via email.

[top]


Useful Links

[top]