Assignments | Course Plan | News |

Cheating | Examination | Prerequisites |

Contact Information | Learning Outcomes | Useful Links |

Content | Literature | Weekly Plan |

Course Evaluation |

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) onWednesday 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]

At Chalmers: link to TMV027 in the studieportalen.

At GU: Pdf with the description of DIT321.

[top]

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]

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]

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

Knowledge and understanding:

- Explain and manipulate the different concepts in automata theory and formal languages such as formal proofs, (non-)deterministic automata, regular expressions, regular languages, context-free grammars, context-free languages, Turing machines;
- Explain the power and the limitations of regular languages and context-free languages.
Skills and abilities:

- Prove properties of languages, grammars and automata with rigorously formal mathematical methods;
- Design automata, regular expressions and context-free grammars accepting or generating a certain language;
- Describe the language accepted by an automata or generated by a regular expression or a context-free grammar;
- Transform between equivalent deterministic and non-deterministic finite automata, and regular expressions;
- Simplify automata and context-free grammars;
- Determine if a certain word belongs to a language;
- Define Turing machines performing simple tasks.
Judgement and approach:

- Differentiate and manipulate formal descriptions of languages, automata and grammars with focus on regular and context-free languages, finite automata and regular expressions.

[top]

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 9781292039053It 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]

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 passboththese parts in order to pass the course.

Since VT15the 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 thatbothparts 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 registeredbefore VT13: Since NO re-exams are offered for that course, these students MUST re-register in the new version of the course and follow theNEWexamination rules.Students who registered in

VT13 or VT14have obligatory assignments and the final grade in the course is that of the exam.

Students who registered in VT13 or VT14 and that haveNOTproduced any points in the course could re-register in the course in VT16 and follow theNEWexamination rules.

Students who registered in VT13 or VT14 and thatHAVEproduced some points in the courseMUSTfollow the examination rules corresponding to VT13/VT14.Students who registered in

VT15have 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]

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]

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]

- Previous year's pages: 2015, 2014, 2013, 2012, 2011, 2010
- Wikipedia
- Short notes 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]