Finite Automata Theory and Formal Languages

TMV027/DIT321, LP4 2013

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


130829: The results of the re-exams are already reported. Please send me an email to book a time if you want to discuss the correction of your exam.

130822: Solution to the exam on August 21st now available.

130614: The student office of the CSE department is already closed for the summer. You might be able to get hold of your exam if you mail them. Otherwise exams will be in my office (6116 in the EDIT building) during Tuesday to Friday in week 26 and you can have a look at it provided I am in my office (which I will most of the time but not all the time!).
Tentagransking will take place on Thursday 27th of June 11-12 in my office. (If many of you come at the same time we move to a closed-by bigger room.) If you cannot make any time next week, just mail me after middle of August so we decide on some time to discuss your exam.

130614: The results of the exams are already reported. Passing rates at both universities were much higher than in previous year (87% at CTH and 72% at GU), I believe due to the introduction of obligatory assignment.

130528: Solution to the exam on May 28th now available.

130528: Protocol from second evaluation meeting available.

130514: When I wrote exercise 1 of assignment 6, I thought of W as one of the variables in the grammar (as in capital letters for variables, small letters for terminals). I see now that this doesn't have to be assumed for W and that one could think of it as one of the terminals in the language.
We will correct this exercise with this in mind, that is, that there are those 2 possibilities for W.
Sorry about this ambiguity.

130514: Information about the second evaluation meeting is now available, check course evaluation.

130422: A google group has been created for the course. Please visit the following link to subscribe.
Post your questions to the following email address

130418: Protocol from first evaluation meeting available.

130417: For some reason I cannot explain, it seems that in connection with a change I made on the heading of assignment 2, the text of exercise 3 changed from "... contain the subword 101" to "... contain the subword 110". Even though I have now changed it back to 101, we will of course, accept solutions to either of both formulations. So don't worry about that and sorry for this change which I cannot really explain...

130412: Information about students representatives and first evaluation meeting is now available, check course evaluation.

130411: Some of you are having problems with Fire.
If you cannot submit your assignment via Fire do mail it to me and Simon.
As I mentioned in the first lecture, we are testing a beta-version. Please do report any problems with Fire to us so we can repair it.

130325: There was an error in ex.3 of Assignment 1: should be "2 node(t) = st (t)". A corrected version is already in place. Sorry about this.

130322: Instructions on how to submit assignments are now available.

130311: To GU students You have to register online at GU Student portal. The registration is obligatory in order to attend the course.
Note that you need to register yourself in the course the same day as the first lecture, otherwise you will lose your place.
For further information about registration and how to activate your student account, click on this link.

130218: Notice that from VT13 this course is divided into 2 courses elements: 1) obligatory weekly written assignments valid 1.5pts and 2) written exam in an examination hall valid 6pts.
Observe that assignments DO NOT generate bonus points from VT13.



Knowledge in mathematics, including a course in Discrete mathematics, and in programming.
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.)
Note: There are 2 typos in the second page on set theory; the right most B in the distributive laws (1) and (2) should be an A.




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

Finite automata (and regular expressions) 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...). Finite automata constitute also a perfect illustration of basic concepts in set theory and discrete structure.

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

Learning Outcomes

After completion of this course, the student should be able to:

Knowledge and understanding:

Skills and abilities: Judgement and approach:



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.)
Note: There are 2 typos in the second page on set theory; the right most B in the distributive laws (1) and (2) should be an A.



There will be obligatory weekly assignments to be done individually. The total amount of points for all assignments will be around 65.
Assignments will NOT generate bonus points from VT2013.

To pass the assignment part of the course you need to individually get at least 50% of the sum of the points of all the weekly assignments together.
For example, if there are 7 assignments during the courses, each with 10pts, you need to have gathered at least 35pts during all your submissions.

Important Note

Be aware that assignments are part of the examination. Hence, standard procedure will be followed if cheating is suspected. Please read carefully the page on cheating and its consequences.

Who should submit?

Chalmers: All of you who are registered in the code TMV027.
GU: All of you who have registered or re-register VT2013.
All other students must not submit. Instead their exam will be 7.5pts and not 6pts like for those who need to do the assignments.

When to submit?

Links to the assignments with preliminary deadlines:

What to submit?

Failure to comply with any of these requirements invalidates your submission, in part or in full.

How to submit?

We will use (a new beta-version of) the Fire system to administrate the submission.

Fire Account: In order to submit any assignment you MUST open an account in Fire by clicking on "register as a student". Fill in the requested information. You will get an email with a confirmation link. After you have clicked on that link your account is ready and can log-in to it.
This must be done only once, before you submit any assignment.

Submission: EACH submission can be done in two different ways:

Whatever method you have used for the submission, once the assignment has been corrected you will get an email with the points you have got in it and possible some comments from the grader.



No books or written help during the exam.

Check the studieportalen for the exam's dates.

Any exercise in the assignments of this course is a typical exam question.
During one of the last lectures we will discuss some old exams (Exam 100527, Exam 100827).
See the schedule for further information.

Here you can find some older exams (you may skip exercise 13 of the first exam) and some solutions (ignore the comments on derivatives in the solutions since we have not covered that).


Course Evaluation

The course should have at least 3-4 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, sometime during the next study period. Representatives from the IT and GU programmes are usually in this last meeting and take notes.

Students representatives CTH: Johan Andersson, mail: johandf(at)
Julia Gustafsson, mail: juliagu(at)
Students representatives GU: Anders Bastos Palomino, mail: gusbastan(at)
Björn Norgren, mail: gusinokibj@(at)

First meeting: Tuesday 16th of April at 12:00. Protocol.
Second meeting: Wednesday 15th of May at 15:15. Protocol.
Additional comments: inform from the start about the max. nr of points in assignments, fixed the time for guest lectures before the day so people can choose whether to go or not.


Contact Information

Lecturer: Ana Bove, mail: bove(at)chalmers(dot)se
Assistants: Pablo Buiras, mail: buiras(at)chalmers(dot)se and
Simon Huber, mail: simonhu(at)chalmers(dot)se

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


Useful Links