Finite Automata Theory and Formal Languages

TMV027/DIT321, LP4 2016


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

News

160830: Exams are now corrected. You can have a look at your exam at the Student office at CSE department. If you want to discuss the correction with me (not how many points each answer is worth!), please send me a mail to book at time. Be aware that a the grade is modified only if an error in the correction has taken place.

160822: Here is a tentative solution for the exam on August 17th.

160615: Soon you should be getting the result of the exam. Student office at CSE department is now closed for the summer. If you want to look at your exam before the Autumn term you can pass by my office (room 6116, EDIT-building) on Wednesday 22/6 10-12.

160602: Here is a tentative solution for the exam on June 1st.

160524: The protocol from the second evaluation meeting is now available under the section on course evaluation.

160510: The second evaluation meeting will take place on Thursday 19th May at 15:00. Please get in touch with me (Ana) or with any of the course representatives with your comments.

160424: The protocol from the first evaluation meeting is now available under the section on course evaluation.

160412: The first evaluation meeting will take place on Thursday 14th April at 15:00. Please get in touch with me (Ana) or with any of the course representatives with your comments.

160330: The course mailing list has been created. All students registered in the course before this date should have received a mail with information on how to access their account.
Those who register to the course after this date need to follow the instructions under contact information on how to register to this list.

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

It also seems the electronic copy of the book is available for free through the library.

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: Since NO re-exams are offered for that course, these students MUST 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 VT16 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.

Students who registered in VT15 have exactly the same examination rules as those registered this year.

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.

Dates of the exams during 2016: 1 June efternoon and 17 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 registered VT13 or later 6 hp 3: >=27, 4: >= 38, 5: >= 49 G: >=27, VG: >= 45

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.

Link to last year's evaluation: Protocol last meeting 2014/2015.
Students representatives at Chalmers: Lage Bergman, mail: lageb(at)student(dot)chalmers(dot)se
Nicklas Lallo, mail: lallo(at)student(dot)chalmers(dot)se
Erik Sievers, mail: eriksie(at)student(dot)chalmers(dot)se
Therese Sturesson, mail: thestu(at)student(dot)chalmers(dot)se
Students representatives at GU: Johan Berndtsson, mail: gusberjodo(at)student(dot)gu(dot)se
Anders Christiansson, mail: guschranh(at)student(dot)gu(dot)se
Kamil Miller, mail: gusmilleka(at)student(dot)gu(dot)se
Filip Wallden, mail: guswalfi(at)student(dot)gu(dot)se

First meeting: Thursday 14th of April at 15:00. Protocol.
Second meeting: Thursday 19th od May at 15:00. Protocol.

[top]

Contact Information

Lecturer and examiner: Ana Bove, mail: bove(at)chalmers(dot)se
Assistants: Pablo Buiras, mail: buiras(at)chalmers(dot)se,
Victor López, mail: lopezv(at)chalmers(dot)se,
Daniel Schoepe, mail: schoepe(at)chalmers(dot)se
Marco Vassena, mail: vassena(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

By the beginning of the second week, all those students registered in the course 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]