**Lectures** (28 times)

- Period 1 (7.9.-21.10.2016):
- 10:15-12:00 Wednesday (Room M3, Quantum)

- 10:15-12:00 Friday (Room M3, Quantum)

- 10:15-12:00 Wednesday (Room M3, Quantum)
- Period 2 (2.11.-16.12.2016):
- 10:15-12:00 Wednesday (Room M1, Quantum)

- 10:15-12:00 Friday (Room M3, Quantum)

- 10:15-12:00 Wednesday (Room M1, Quantum)

- Periods 1 and 2 (12.9.-17.10.2016 and 31.10.- 12.12.2016):
- 14:15-16:00 Monday (Room M3, Quantum)

- 14:15-16:00 Monday (Room M3, Quantum)

**Course Web Page:**

**Instructor:**

- Jarkko Kari
- Office: Quantum 3rd floor, room 365

- email: jkari@utu.fi,

- tel: (02) 333 5616.

- Office hours: Thursday 10-11am

- No texbook. Lecture notes are posted on the course web page.

- Presence is mandatory. Absence is permitted only if agreed with the lecturer (ask beforehand if possible).
- To pass the course, at least 25% of the homework problems must be completed. The more problems you solve, the more credit towards the final grade you get: You get demo class
- A, if you complete 70%-100%,
- B, if you complete 45%-70%,
- C, if you complete 25%-45%

- Two midterms: Oct 27 at 9:00-12:00 and Dec 19 at 14.00-17:00.
- Not mandatory. The class requirements can also be satisfied by taking a single final exam.
**Registration though internet (NettiOpsu) is required at least one week before the exam.**- Both midterms (3 hours) consist of 4 problems, each of which has maximum score of 4 point.
- A minimum of 5 points is required in both midterms.
- Homework activity (demo class A, B or C) and the combined score of the two midterms determine the final grade according to the following table:

Final Grade

Demo class

A

B

C

**1**13-14

14-15

15-16

**2**15-18

16-19

17-20

**3**19-22

20-23

21-24

**4**23-27

24-28

25-28

**5**28-32

29-32

29-32

- An alternative way to pass the class. One can take the exam more than once (even if one has passed the course) to improve the final grade.
- Registration though internet (NettiOpsu) is required at least one week before the exam.
- Anyone with democlass at least C has qualified to take the exam within one year.
- Exams (4 hours) consist of 5 problems, each of which has maximum score of 8 points.
- Homework activity (demo class A, B or C) and the score of the final exam determine the final grade according to the following table:

Final Grade

Demo class

A

B

C

**1**17-18

18-19

19-21

**2**19-23

20-24

22-26

**3**24-29

25-30

27-31

**4**30-34

31-35

32-36

**5**35-40

36-40

37-40

**Brief course outline**

- Regular languages
- Finite automata, regular expressions
- Kleene theorem
- Pumping lemma
- Closure properties and decision algorithms
- State minimization, Myhill-Nerode theorem

- Context-free languages
- Grammars, parsing
- Normal forms
- Pushdown automata
- Pumping lemma
- Closure properties and decision algorithms

- Turing machines
- Recursive and recursively enumerable languages
- Universal Turing machines
- Undecidability of the halting problem (Turing)
- Reductions, other undecidable problems