[ News | Prerequisites | Goals | Literature | Assignments | Schedule | Exam | Course Evaluation | Contact Information | Useful Links ]
130829: The results of the re-exams are already reported. Please send me an email to book a time if you want to discuss the correction of your exam.130822: Solution to the exam on August 21st now available.
130614: The student office of the CSE department is already closed for the summer. You might be able to get hold of your exam if you mail them. Otherwise exams will be in my office (6116 in the EDIT building) during Tuesday to Friday in week 26 and you can have a look at it provided I am in my office (which I will most of the time but not all the time!).
Tentagransking will take place on Thursday 27th of June 11-12 in my office. (If many of you come at the same time we move to a closed-by bigger room.) If you cannot make any time next week, just mail me after middle of August so we decide on some time to discuss your exam.130614: The results of the exams are already reported. Passing rates at both universities were much higher than in previous year (87% at CTH and 72% at GU), I believe due to the introduction of obligatory assignment.
130528: Solution to the exam on May 28th now available.
130528: Protocol from second evaluation meeting available.
130514: When I wrote exercise 1 of assignment 6, I thought of W as one of the variables in the grammar (as in capital letters for variables, small letters for terminals). I see now that this doesn't have to be assumed for W and that one could think of it as one of the terminals in the language.
We will correct this exercise with this in mind, that is, that there are those 2 possibilities for W.
Sorry about this ambiguity.130514: Information about the second evaluation meeting is now available, check course evaluation.
130422: A google group has been created for the course. Please visit the following link to subscribe.
Post your questions to the following email addresschalmers-fatfl@googlegroups.com.130418: Protocol from first evaluation meeting available.
130417: For some reason I cannot explain, it seems that in connection with a change I made on the heading of assignment 2, the text of exercise 3 changed from "... contain the subword 101" to "... contain the subword 110". Even though I have now changed it back to 101, we will of course, accept solutions to either of both formulations. So don't worry about that and sorry for this change which I cannot really explain...
130412: Information about students representatives and first evaluation meeting is now available, check course evaluation.
130411: Some of you are having problems with Fire.
If you cannot submit your assignment via Fire do mail it to me and Simon.
As I mentioned in the first lecture, we are testing a beta-version. Please do report any problems with Fire to us so we can repair it.130325: There was an error in ex.3 of Assignment 1: should be "2 node(t) = st (t)". A corrected version is already in place. Sorry about this.
130322: Instructions on how to submit assignments are now available.
130311: To GU students You have to register online at GU Student portal. The registration is obligatory in order to attend the course.
Note that you need to register yourself in the course the same day as the first lecture, otherwise you will lose your place.
For further information about registration and how to activate your student account, click on this link.130218: 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.
Observe that assignments DO NOT generate bonus points from VT13.
[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 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...). Finite automata constitute also a perfect illustration of basic concepts in set theory and discrete structure.
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'.
Learning Outcomes
After completion of this course, the student should be able to:Knowledge and understanding:
Skills and abilities:
- 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.
Judgement and approach:
- 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 obligatory weekly assignments to be done individually. The total amount of points for all assignments will be around 65.
Assignments will NOT generate bonus points from VT2013.To pass the assignment part of the course you need to individually get at least 50% of the sum of the points of all the weekly assignments together.
For example, if there are 7 assignments during the courses, each with 10pts, you need to have gathered at least 35pts during all your submissions.
Important Note Be aware that assignments 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.
Who should submit? Chalmers: All of you who are registered in the code TMV027.
GU: All of you who have registered or re-register VT2013.
All other students must not submit. Instead their exam will be 7.5pts and not 6pts like for those who need to do the assignments.
When to submit? Links to the assignments with preliminary deadlines:
- Deadline Thursday 11/4 23:59: Assignment-1 on Formal proofs (10 pts);
- Deadline Thursday 18/4 23:59: Assignment-2 on DFA and NFA (10 pts);
- Deadline Thursday 25/4 23:59: Assignment-3 on epsilon-NFA and RE (9.5 pts);
- Deadline Friday 3/5 23:59: Assignment-4 on regular languages (10.5 pts);
- Deadline Monday 13/5 23:59: Assignment-5 on context free-grammars (10 pts);
- Deadline Monday 20/5 23:59: Assignment-6 on context-free languages (10 pts);
- Deadline Sunday 26/5 23:59: Assignment-7 on Turing machines (4 pts).
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, even if the submission is done completely electronically.
- 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.
- If you write your solution by hand, make sure your hand-writing is legibly: what we cannot read we cannot grade!
How to submit? We will use (a new beta-version of) the Fire system to administrate the submission.
Fire Account: In order to submit any assignment you MUST open an account in Fire by clicking on "register as a student". Fill in the requested information. You will get an email with a confirmation link. After you have clicked on that link your account is ready and can log-in to it.
This must be done only once, before you submit any assignment.Submission: EACH submission can be done in two different ways:
Whatever method you have used for the submission, once the assignment has been corrected you will get an email with the points you have got in it and possible some comments from the grader.
- Electronically using the Fire system. You should attach all necessary files to your submission. Only pdf or plain text are valid formats. Observe that scanned versions of hand-written solutions are valid electronic solutions.
This is the preferred submission method since it is secure and simple.
- Personally 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).
Once the teacher in question gets to his/her office, he/she will inform the Fire system that your submission has been done. You will then get an email confirming your submission.
Important Notes:
- You should create a Fire account before you submit any assignment to us personally. If we cannot find you in the system we cannot register your submission and it will be discarded.
- Your submission is actually NOT done until the teacher indicates to the system he/she has received your submission.
- Contact us immediately if a few hours after you have submitted in this way you have yet NOT received any confirmation mail from the system.
- We take NO responsibility for lost submission before they are registered in the system. If you want to make sure no submission is lost please consider making an electronically submission.
- If the submission doesn't contain the necessary identification information (see information on "What to submit"), it will automatically be discarded.
- If your submission has 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.
[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.
During one of the last lectures we will discuss some old exams (Exam 100527, Exam 100827).
See the schedule for further information.Here you can find some older exams (you may skip exercise 13 of the first exam) and some 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. 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 in this last meeting and take notes.
Students representatives CTH: Johan Andersson, mail: johandf(at)student.chalmers.seJulia Gustafsson, mail: juliagu(at)student.chalmers.seStudents representatives GU: Anders Bastos Palomino, mail: gusbastan(at)student.gu.seBjörn Norgren, mail: gusinokibj@(at)student.gu.seFirst meeting: Tuesday 16th of April at 12:00. Protocol.
Second meeting: Wednesday 15th of May at 15:15. Protocol.
Additional comments: inform from the start about the max. nr of points in assignments, fixed the time for guest lectures before the day so people can choose whether to go or not.
[top]
Lecturer: Ana Bove, mail: bove(at)chalmers(dot)seAssistants: Pablo Buiras, mail: buiras(at)chalmers(dot)seand
Simon Huber, mail:simonhu(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: 2012, 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]