[ News | Prerequisites | Goals | Literature | Assignments | Schedule | Exam | Course Evaluation | Contact Information | Useful Links ]
120914: I am afraid I need to cancel the tentagranskning. Please drop me an email if you want to discuss your exam so we can agree on a suitable time.120910: Before the end of the week you should receive the results of the exam. There will be a tentagranskning on Monday 17th at 12:00 in my room 6116 in the EDIT building.
OBS: Cancelled!120903: Solutions to the exam on 120831.
120611: Before the end of the week you should receive the results of the exam. There will be a tentagranskning on Monday 18th at 13:00 in room 6128 in the EDIT building.
120525: Solutions to the exam on 120525.
120521: On Tuesday 22nd of May from 10-12 there will be a consultation time in EL41. (If the room is occupied we take EL42 or EL43.)
120521: The protocol of the evaluation meeting on May 10th is now available.
120504: The second evaluation meeting will take place on Thursday 10th of May at 12.00. Please send your comments to the students representatives (see course evaluation for their email addresses).
120418: The protocol of the evaluation meeting on March 29th is now available.
120322: The first evaluation meeting will take place on Thursday 29th of March at 12.00. Please send your comments to the students representatives (see course evaluation for their email addresses).
120313: Exercise classes has been moved to a bigger room. See page on schedule for more information.
[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]
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...).
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'.
After completion of this course, the student should be able to:
- 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;
- Have a clear understanding about the equivalence between deterministic and non-deterministic finite automata, and regular expressions;
- Acquire a good understanding of the power and the limitations of regular languages and context-free languages;
- 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;
- Simplify automata and context-free grammars;
- Determine if a certain word belongs to a language;
- Define Turing machines performing simple tasks;
- 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.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]
There will be non-obligatory weekly assignments to be submitted individually and that will generate bonus points valid only on the exams during 2012.Each assignment will be up to 10 pts. If a student has collected n pts in assignments, this will correspond to n/10 points in the exam. Exams are usually 60 points.
See the schedule page for the actual assignments and their deadlines.
How to submit? You can submit an assignment solution in two different ways:
- On paper to any of the teachers of the course in connection to the lectures, exercises or consultation times, or at Ana's office (room 6116 of the D&IT building).
If your submission is more than 1 page, then the pages must be stapled, or securely clipped, together, in the top-left corner only (no plastic-pocketed, rolled, folded, taped, or glued submissions). We take no responsibility for lost pages.
Please make sure your hand-writing is legibly: what we cannot read we cannot grade!
- On a file using the Fire system. Only pdf or plain text are valid formats.
To access the course account in the fire system click here.
You need to register yourself by clicking on "register as a student" and filling in the requested information. You will get an email with further instructions. Then you log-in using the account you have created.
Further information about how to use the Fire system can be found here.When to submit? Any time before 23.59 on the day of the deadline.
What to submit?
Failure to comply with any of these requirements invalidates your submission, in part or in full.
- You must write your name, personal number and e-mail address in the assignment you submit.
- You must have thought and written the solution on your own.
- You can write either in English or in Swedish.
- Any non-trivial claim must be supported with a justification/proof or with the proper reference to the book/slides of the course.
- Solutions should be presented in a coherent and clear manner.
Important Note Be aware that, since assignments give bonus points to be used in the exam, they 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.
[top]
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.
This link shows a couple of old exams. We will discuss them in one of the lectures during the last week of the course.
Notes:
- Exercise 13 of the first exam (date 2007-05-31) is not applicable for the course this year;
- These exams have a total of 30 points; the exam for this course will have a total of 60 points. (You can in most cases simply multiply by 2 the points of each exercise to obtain the points of the exercise in our exam.)
[top]
The course should have at least 2 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. A representative from the IT program is usually in this last meeting and takes notes.
Students representatives: Daniel Bergqvist, danber(at)student.chalmers.se
Marika Hansson,hmarika(at)student.chalmers.se
Magnus Larsson,maglars(at)student.chalmers.se
Marcus Stigelid,stigelid(at)student.chalmers.se
The protocol of the evaluation meeting on March 29th is now available.
The protocol of the evaluation meeting on May 10th is now available.
The protocol of the last evaluation meeting on October 3rd is now available.
[top]
Lecturer: Ana Bove, mail:bove(at)chalmers(dot)se
Assistant: Willard Rafnsson mail:willard(dot)rafnsson(at)chalmers(dot)seFeel free to contact us if you have any further questions, either after the lectures/exercise sessions or via email.
[top]
- Previous year's pages: 2011, 2010, 2009
- 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]