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

140829:The exams are corrected and you should have already got the result. You can look at the correction at the student expedition any time it is open. If you want to discuss the correction with me, please send me an email with your name and personal number so we book a time for this.

140821:Suggested solution for the exam on August 20th 2014.

140528:Suggested solution for the exam on May 28th 2014.

140520:Protocol for the second evaluation meeting is now available. Check section on course evaluation.

140505:The second evaluation meeting will take place on Thursday 15th of May at 15:15. Contact me (Ana) or any student representative if you have any comments you would like us to discuss.

140429:There will be a consultation time on 30/4 13:15-15:00 in ES51 (or EC) and an exercise class on Friday 2/5 15:15-17 in EF. Check page with weekly plan for more information.

140429:Deadline for assignment 4 has been moved to Monday 5/5 at 23:59.

140411:Protocol for the first evaluation meeting is now available. Check section on course evaluation.

140325:All those registered to the course should have got a mail with the registration to the mailing list of the course`fafl(at)lists(dot)chalmers(dot)se`

. If not please visit this page to register.

Be aware you can only post to the list with the mail address you have been registered to.

Before sending a mail to the list, make sure the question/comment concerns ALL the student in the course. If not, it is better just to mail me (Ana).

140324:The first evaluation meeting will take place on Monday 7th of April at 15:15. Contact me (Ana) or any student representative if you have any comments you would like us to discuss.

140324:The last exercise in assignment 1 contained an error: one should prove thatrev(rev(x)) = x! It is already corrected in the pdf that is linked now.

140306:Since the course got many more students than expected the schema has been changed. Check the page with the weekly plan for more information.

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

[top]

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.

[top]

## Content

This course presents both the theory of finite automata, regular expressions and context-free grammars. If time allows, 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'.

## Learning Outcomes

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. Check this if you are interested.

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.

[top]

No books or written help during the exam.

Day of the exams:28 May and 20 Aug 2014.

Check the studieportalen for the exam's times and locations.

Grade information:The table below shows the nr of points you need to get in the exam in order to obtain a certain grade. 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 we will discuss last year's exams (Exam 130528, Exam 130821).

See the weekly plan for further information.Here you can find some older exams: Exam 100527 with solutions, Exam 100827 with solutions and exams from 2007 (you may skip exercise 13 of the first exam) with solutions (ignore the comments on derivatives in the solutions since we have not covered that).

[top]

The course should have at least 3-4 students representatives from both universities. 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 present in this last meeting and take notes.

Students representatives CTH: Julia Friberg, mail: `frjulia(at)student(dot)chalmers(dot)se`

Emma Gustafsson, mail: `guemma(at)student(dot)chalmers(dot)se`

Christoffer Henriksson, mail: `chrhen(at)student(dot)chalmers(dot)se`

Pontus Malm, mail: `malmpo(at)student(dot)chalmers(dot)se`

Students representatives GU: Hossein Hussain, mail: `hossein(dot)hussain(at)me(dot)com`

Alexander Reinthal, mail: `alexander(dot)reinthal(at)gmail(dot)com`

Jonathan Skårstedt, mail: `jonathan(dot)skarstedt(at)gmail(dot)com`

First meeting April 8th 2014:Protocol

Second meeting May 15th 2014:Protocol

[top]

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`

,

Inari Listenmaa, mail:`inari(at)chalmers(dot)se`

,

Daniel Hausknecht, mail:`daniel(dot)hausknecht(at)chalmers(dot)se`

and

Andrea Vezzosi, mail:`vezzosi(at)chalmers(dot)se`

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

## Course Mailing List

All those registered to the course should have got a mail with the registration to the mailing list of the course`fafl(at)lists(dot)chalmers(dot)se`

. If not please visit this page to register.

Be aware you can only post to the list with the mail address you have been registered to.

Before sending a mail to the list, make sure the question/comment concerns ALL the student in the course. If not, it is better just to mail me (Ana).

[top]

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

[top]