Talen en Automaten (NWI-IPC002), lectures, 2nd quarter, Fall 2016

The lectures will be given by Herman Geuvers and Jurriaan Rot. All course material will be in English. Information about exercises will be given on a separate exercise page.

Lectures will be on Tuesday afternoon, 13:45-15:30. The first lecture will be on November 8, and the last one on January 10.

Prerequisites consist of (secondary) school mathematics.

Course material consists of:

• Languages and Automata Lecture notes called LnA below, written by Alexandra Silva, with some additions by Herman Geuvers.
• Everything the teachers write on the blackboard during the lectures,
• Slides, which are being produced as the course proceeds. See below.

Your final grade for this course will be composed from the half-way test grade, T1, the final test grade, T2, and the assignment grade, A.

• weekly exercises are compulsory to hand in: your answers will be marked each week, and at the end of the course we compute the average of your marks; this average will constitute the assignment grade A. You must submit individually (not in pairs), see the exercise page for the exercises;
• the half-way test on Tuesday December 13, 13:30-15:30 constitutes your half-way test grade T1.
• the final test (Wednesday January 18, 8:30-11:30) constitutes your final test grade T2.
• the final grade for the course is the average of the 2 test grades plus 10% of the assignment grade (with a maximum of 10):
  min(10, (T1+T2)/2 + A/10).

All students who have already done the exam for this course twice, unsuccesfully, will be required to do the following before they obtain the right to do the exam again:

• Talk to the study advisor; it is advised to contact him/her as soon as possible to schedule a meeting;
• Talk to the teacher to fill in a form;
• Attend all lectures and exercise classes.

Schedule

1. lecture 1, Tuesday 8/11, 13:45-15:30, HG00:307,
   • Topic: Regular Languages: words, operations on words, languages, regular languages, regular expressions, proofs by induction, Chapter 1 and Section 2.1.
   • Slides: pdf
2. lecture 2, Tuesday 15/11, 13:45-15:30, HG00:307
   • Topic: Deterministic finite automata (DFA): Accepting words, accepting a language, from DFAs to regular expressions, Sections 2.2 and 4.2.2.
   • Slides: pdf
3. lecture 3, Tuesday 22/11, 13:45-15:30, HG00:307
   • Topic: Non-deterministic finite automata (NFA): Accepting words, accepting a language, removing non-determinism; from NFAs to DFAs, from regular expressions to NFAs.
   • Slides: pdf
4. lecture 4, Tuesday 29/11, 13:45-15:30, HG00:307
   • Topic: Non-regular languages: Pumping lemma, closure properties for the class of regular languages.
   • Slides: pdf
5. lecture 5, Tuesday 6/12, 13:45-15:30, HG00:307
   • Topic: Grammars: Context Free and Regular Grammars
   • Slides: pdf
6. Test 1, Tuesday 13/12, 13:30-15:30.
   • Here are test1 of 2015 and test2 of 2015, and here are the answers, with the answer to 4c of test1 here separately. (Note: in 2015, the "pumping lemma" was in test2, but in 2016 it is in test1.)
   • Make sure you are registered for the course
   • Be present at 13:15 at the very latest.
   • Topic: Halfway Test on Lectures 1--4.
   • Locations for the Test:
     • names A -- G: HG00.307
     • names H -- M: HG00.071
     • names N -- Z: LIN 3
     • extra time students: HG00.086
7. lecture 6, Tuesday 20/12, 13:45-15:30, HG00:307
   • Topic: Push-down automata: from CF grammars to Push-down automata and back.
   • Slides: pdf
8. lecture 7, Tuesday 10/1, 13:45-15:30, LIN1
   • Topic: Chomsky hierarchy: Context-Sensitive Grammars and recursive languages; Lindenmayer systems.
   • Slides: pdf
9. Question time: Tuesday 17/1, 13:45-14:30 in HFML0220
   • Topics: Question time, handing back assignment 7, old assignments, old exam.
   • The second test of 2015-2016, not completely representative for the material of this year. (The Pumping Lemma wasn't in test1; this year we also treated translations between PDAs and CFGs.)
   • Answers to the second test of 2015-2016.

Exam

• The half-way test takes place on Tuesday December 13, 13:30-15:30.
• the final test takes place on Wednesday January 18, 8:30-11:30.
• The second chance is: Wednesday March 1, 18:00-21:00.
• Here is the reexam of last year. Try it under exam conditions (put away your notes, make it in 3 hrs). Here is the reexam of last year with answers.