Finite Automata Theory and Formal Languages

TMV027/DIT321, LP4 2015


Assignments Course Plan News
Cheating Examination Prerequisites
Contact Information Learning Outcomes Useful Links
Content Literature Weekly Plan
Course Evaluation


News

150831: Here are some suggested solutions to the exam on August 19th.
150618: Exams are already corrected and you should find the information in Ladok.
Student office is now closed for the summer so you will not be able to look at your exam there. Instead, I will have the exams in my room (6116 in the EDIT building) so you can come and look at it there, and also ask me if you have any questions.
WHEN can you come? Tuesday 13-17 or Wednesday, Thursday or Friday 11-17. I will NOT be in my room all the time though but I will leave my telephone nr in the door so you can phone me so I come back to my room to meet you.
150603: Here are some suggested solutions to the exam on June 3rd.
150527: There will be an extra consultation class on Monday 1st of June 15:15-17:00 in room ES53.
150525: The protocol of the second evaluation meeting on May 13th is now available. Please visit the part on Course Evaluation.
150507: The second course evaluation meeting will take place on Wednesday 13/5 at 12:00. Please check the section on Course Evaluation for the information on how to contact the student representatives. You are also welcome to send/give your comments to me (Ana).
150430: The protocol of the first evaluation meeting on April 2nd is now available. Please visit the part on Course Evaluation.
150327: The first course evaluation meeting will take place on Thursday 2/4 at 11:00. Please check the section on Course Evaluation for the information on how to contact the student representatives. You are also welcome to send/give your comments to me (Ana).
150326: The lecture on Monday 30/3 has been moved to HC2.
150325: Those students registered in the course by Wednesday morning should have got a registration to the mailing list of the course. If for some reason you have not got a mail with your registration to the mailing list please visit this page and register there.
150213: From VT15 the final grade in the course is based on the performance on both the assignments and the exam. Read more about this in the section on Examination.

[top]

Course Plan

At Chalmers: link to TMV027 in the studieportalen.
At GU: Pdf with the description of DIT321.

[top]

Prerequisites

Knowledge in Discrete mathematics and in programming.

Here one can find some short notes to refresh the knowledge on basic notions like sets, relations and functions. (The responsible of the course 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.

[top]

Content

This course presents both the theory of finite automata, regular expressions and context-free grammars. It also includes a short introduction to Turing machines.

Finite automata and regular expressions are one of the first and simplest models of computations. Their mathematical theory is quite elegant and simple. Finite automata are widely used in applications (traffic light, lexical analysis, pattern search algorithm, etc...), and constitute a perfect illustration of basic concepts in set theory and discrete structure.

Context-free grammars have important applications in parsing and analysis of both programming and natural language.

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]

Learning Outcomes

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

Knowledge and understanding:

Skills and abilities: Judgement and approach:

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

This is how some of the possible versions of the 3rd edition of the book look like:
ISBN 9780321455369 ISBN 9780321476173 ISBN 9781292039053
ISBN 9780321455369 -- ISBN 9780321476173 -- ISBN 9781292039053

It seems it might be an electronic version of the book that one can buy from the publisher.

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 one can find some short notes to refresh the knowledge on basic notions like sets, relations and functions. (The responsible of the course 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.

[top]

Examination

Since VT13 the examination of the course consists of 2 parts: weekly assignments valid 1.5 hp (20% of the total hp) and a written exam valid 6 hp (80% pf the total hp).
One needs to pass both these parts in order to pass the course.

Since VT15 the final grade in the course is based on the performance on both the assignments and the exam.
The maximum nr of points to be considered for the final grade is 76: a maximum of 60 coming from the exam (that is, 100% of the total amount of points in the exam) and a maximum of 16 coming from the weekly assignments (that is, 25% of the total amount of the points in the all the assignments together). In this way the weight of each part in the course is proportional to the nr of hp in each of the parts in the course.

The final grade in the course is indicated by the table below where

Final points = nr of points got in the exam + 25% of the points gathered in the assignment

Chalmers:
Grade Final Points
3 35
4 46
5 57
GU:
Grade Final Points
G 35
VG 53

Note: Remember that both parts of the course need to be passed in order to pass the whole course!!

Example: If a student gets 27 points in the exam and 32 points in the assignments, then the final points he/she will obtain are 27 + 0.25 x 32 = 27 + 8 = 35. This student will pass the assignments with G, pass the exam with G or 3 (depending on the university), and pass the course with G or 3.
Example: If a Chalmers student gets 36 points in the exam and 40 points in the assignments, then the final points he/she will obtain are 36 + 0.25 x 40 = 36 + 10 = 46. This student will pass the assignments with G, pass the exam with 3, and pass the course with 4.
Example: If a GU student gets 40 points in the exam and 60 points in the assignments, then the final points he/she will obtain are 40 + 0.25 x 60 = 40 + 15 = 55. This student will pass the assignments with G, pass the exam with G, and pass the course with VG.

Older Students

Students who registered before VT13 have no obligatory assignments. Since not many re-exams will be offered for that course in the future, these students are encourage to re-register in the new version of the course and follow the NEW examination rules.

Students who registered in VT13 or VT14 have obligatory assignments and the final grade in the course is that of the exam.
Students who registered in VT13 or VT14 and that have NOT produced any points in the course could re-register in the course in VT15 and follow the NEW examination rules.
Students who registered in VT13 or VT14 and that HAVE produced some points in the course MUST follow the examination rules corresponding to VT13/VT14.

Weekly Assignments

There will be 7 assignments and the total amount of points for all assignments together will be 64 points.
To pass the assignment part of the course one needs to get at least 50% of the sum of the points of all the weekly assignments together, that is, one needs to get at least 32 points in total.

Each assignment will be made available not later than 1 week before the deadline.

For more information about the weekly assignments please visit this page.

Exam

No books or written help during the exam.

Day of the exams during 2015: 3 June efternoon and 19 August morning.
Check the studieportalen for the exam's locations and possible updates.

Grade information: The table below shows the nr of points one needs to get in the exam in order to obtain a certain grade in the exam. The total nr of points in the exam is 60.

Registration Code Nr of hp Chalmers GU
TMV027 or DIT321 with registration VT13 or later 6 hp 3: >=27, 4: >= 38, 5: >= 49 G: >=27, VG: >= 45
TMV026 or DIT321 with registration before VT13 7.5 hp 3: >=33, 4: >= 43, 5: >= 53 G: >=33, VG: >= 50

Any exercise in the assignments of this course is a typical exam question.
During one of the last lectures, 2013's exams will be discussed in class (Exam 130528, Exam 130821).
See the weekly plan for further information.

Here one can find some older exams: Exam 100527 with solutions, Exam 100827 with solutions and exams from 2007 (one may skip exercise 13 of the first exam) with solutions (one should ignore the comments on derivatives in the solutions since that part was not covered in the course).

[top]

Course Evaluation

The course should have at least 3-4 students representatives from each university. The students representatives will meet the responsible of the course a couple of times during the study period 4. In these meetings the student representative should write the minutes. The final meeting takes place after the exam, sometime during the next study period. Representatives from the IT and GU programmes are usually present in this last meeting and take notes.

Students representatives at Chalmers: David Gustafsson, mail: davgusta(at)student(dot)chalmers(dot)se
Christoffer Sandlund, mail: chrsand(at)student(dot)chalmers(dot)se
Lisa Lipkin, mail: lipkin(at)student(dot)chalmers(dot)se
Students representatives at GU: Niclas Krause, mail: guskrauni(at)student(dot)gu(dot)se
Andreas Widbom, mail: guswidban(at)student(dot)gu(dot)se

First meeting: Thursday 2nd of April at 11:00. Protocol.
Second meeting: Wednesday 13th od May at 12:00. Protocol.

[top]

Contact Information

Lecturer: Ana Bove, mail: bove(at)chalmers(dot)se
Assistants: Pablo Buiras, mail: buiras(at)chalmers(dot)se,
Simon Huber, mail: simonhu(at)chalmers(dot)se,
Daniel Schoepe, mail: schoepe(at)chalmers(dot)se     and
Andrea Vezzosi, mail: vezzosi(at)chalmers(dot)se

Feel free to contact any of us, either after the lectures/exercise sessions or via email.

Course Mailing List

At the beginning of the course, all those students registered in it will be registered to the mailing list of the course fafl(at)lists(dot)chalmers(dot)se. A mail confirming the registration and containing log-in information to the Mailman administrative interface will be sent to each student.
Those students who don't get such mail please visit this page to register.
Be aware one can only post to the list with the mail address one has been registered to the list.
Note: The mailing list is being moderated to make sure that only mails concerning all/many students are sent to the list.
Questions that only concern a particular students should be sent directly to me (Ana).

[top]

Useful Links

[top]