Finite Automata Theory and Formal Languages

TMV026/DIT321, LP4 2011


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


News

110912: At any moment you can go to the student office (provided they are open) and look at your exam. If you want to discuss it with me please drop me a mail to book a time.

110912: Exams are now corrected. GU students should be able to see the result in a couple of days, it takes a couple of extra days at CTH.

110830: Solutions for the exam on 110826 are now available.

110616: Exams are now corrected. GU students should be able to see the result tomorrow, it takes a couple of extra days at CTH.

110530: "Tentagranskning" for the course will take place on June 22nd 11-12 in room 6128 of the EDIT building.

110530: See the table of bonus points after the assignment.
If you name is not there could be because you have not provided your personal number. Please contact me about this after June 10th.
If for some reason the total figure is wrong please contact Willard by e-mail to find out where the problem might be.

110530: Solutions for the exam on 110527 are now available.

110520: See the schedule for week 7 page for solutions to the exams discussed on lecture on May 16th.

110510: On Thursday 19th of May at 12.00 we will have our second evaluation meeting for the course. Make sure you send your comments to either of the students representatives in the course.

110508: Observe the different schedule for week 7.

110502: See section on Exam for a couple of old exams.

110427: Please remember to put your personal number in the assignments you submit. Many of them are missing this information!

110427: Extra consultation class on Thursday 5/5 10-12 in ES51. Please come with concrete questions to discuss!

110412: I believe I wasn't very clear on how to get the equivalent classes of states after we fill the table of distinguishable states. I have asked Ramona to go through this again on the exercise class on Thursday (she will replace Willard this week).

110407: Protocol of the first course evaluation meeting is now available.

110407: Deadline for assignments is at 23:59 the day of the deadline.
Corrected assignments will be distributed during the following exercise class.

110329: On Thursday 7th of April at 12.00 we will have the first evaluation meeting for the course. Make sure you send your comments to either of the students representatives in the course.

[top]

Prerequisites

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

[top]

Goals

This course presents both the theory of finite automata and of pushdown automata. It also includes a short introduction to Turing machines.

Finite automata (and regular languages) are one of the first and simplest model of computations. Its mathematical theory is quite elegant and simple, and finite automata are widely used in applications (traffic light, lexical analysis, pattern search algorithm, etc...).

Pushdown automata are finite automata with stacks. The theory is more complex, but has important applications in parsing and analysis of context-free languages which is also a fundamental concept in computer science.

Turing machines were described by Alan Turing in 1937 and they are a powerful model of computation since they help computer scientists understand the limits of mechanical computation by providing a precise definition of an 'algorithm' or 'mechanical procedure'.

[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 and why they are equivalent.

Here you can find some short notes to refresh your knowledge on basic notions like sets, relations and functions.
(We would like to thank Einar Steingrímsson for these notes.)

[top]

Assignments

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

Each assignment will be up to 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.

Note: 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.

How to Submit Assignments:

[top]

Exam

No books or written help during the exam.

Check the studieportalen for information about the exam.

Any exercise in the assignments of this course is a typical exam question.
This link shows a couple of old exams. We will discuss them in one of the lectures during the last week of the course.
Notes:

[top]

Course Evaluation

The course should have at least 2 students representatives. During the course we should meet a couple of times. In these meetings the student representative should write the minutes. The final meeting should be done after the exam. A representative from the IT program is usually in the meeting and takes notes.

Contact information for the student representatives for this year:

Protocol of the first course evaluation meeting is now available.

Here you can find a summary from the course evaluation from LP4 2010 (only accessible from Chalmers network).

[top]

Contact Information

Lecturer: Ana Bove, mail: bove(at)chalmers(dot)se
Assistant: Willard Rafnsson mail: willard(dot)rafnsson(at)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]