There will be exercise sessions as well as “consultation time”, and you can also work on exercises on your own. In the exercise sessions solutions to selected exercises from the exercise sets below will be presented (possibly with some interaction). Consultation time is more flexible: the participants can decide together what to work on. This might involve solving certain exercises, revising a topic, or something else.
| Week | Exercise set | Description | Selected exercises (preliminary) |
|---|---|---|---|
| 1 | E0 | Logic, sets, relations and functions (repetition). | Logic: 4, 11. Sets: 5, 6, 8g. Relations: 3, 5, 8ae. Functions: 4, 7, 8. |
| 2 | E1 | Formal proofs, alphabets and words. | Proofs by Counterexample and Contradiction: 1. Mathematical and Course-of-values Induction: 1, 6, 7, 8. Mutual Induction: 2. Alphabets, Words, and Induction: 2, 3. Inductive Sets and Structural Induction: 1. |
| 3 | E2 | DFAs, NFAs and ε-NFAs. | DFA, basic: 2, 4. Additional: 2 (2.2.11). NFA, basic: 1, 3. Additional: 3. |
| 4 | E3 | Regular expressions. | Basic: 1, 3. Additional: 1, 3.2.3, 3.2.5, 3.4.1. |
| 5 | E4 | Regular languages. | Basic: 1de, 2, 4 (4.4.1). Additional: 1, 2 (4.1.1c, 4.1.4c). |
| 6 | E5 | Context-free grammars. | Basic: 5.1.1ab, 5.1.3, 5.4.1, 5.4.3. Additional: 5.1.6, 5.2.2, 5.4.2. |
| 7 | E6 | Context-free languages. | Basic: 1, 2. Additional: 1 (7.1.1), 3 (7.2.2). |
| 8 | E7 | Turing machines. | Basic: 1, 2a. Additional: 1, 2b. |
The exercise sets might be modified during the course. Note also that the exercises were written for a previous instance of the course, and include a small number of references to lectures that may be inapplicable to this instance of the course.
Solutions are available to the starred exercises from the course text book. JFLAP can perhaps be of help for some exercises.