AFL course syllabus

 

Autumn semester 2026
Automata and Formal Languages

 

The course has two parts:

  • Part 1 on Sep 7 – Oct 23,
  • Part 2 on Oct 26 – Dec 18.

The first part alone forms a 5ects course, the two parts combined form a 10ects course.

 

Lectures:

  • 10:15-12:00 Tuesdays in room M3 (Quantum, 3rd floor)
  • 10:15-12:00 Thursdays in room M2 (Quantum, 2nd floor)

Homework sessions:

  • 14:15-16:00 Mondays in room M1 (Quantum, 2nd floor)

Course Web Page: http://users.utu.fi/jkari/afl2026

Instructor:  Jarkko Kari <jkari@utu.fi>; office: Quantum 365, 3rd floor

Textbook:

  • No textbook. Lecture notes are posted on the course web page.

About homework:

  • 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%

      of the given problems.

Grading the 5ects course:

  • An exam at the end of the first teaching period (on Monday, October 19, at 9:30-12:30, in room M3)
  • The 3 hour exam consists of 4 problems, each of which has a maximum score of 4 points.
  • The homework activity (demo class A, B or C) and the score of the exam determine the final grade according to the following table:

Final Grade

Demo class

A

B

C

1

6-7

7

7-8

2

8-9

8-10

9-10

3

10-11

11

11-12

4

12-13

12-14

13-14

5

14-16

15-16

15-16

Grading the 10ects course:

Midterms

  • The 10ects course has two midterm exams, at the ends of both parts.  The first midterm exam is the same as the final exam of the 5ects course (on Monday, October 19, at 9:30-12:30, in room M3).
  • Not mandatory on the 10ects course. The class requirements can also be satisfied by taking a single final exam after Part 2.
  • 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

Final exam:

  • An alternative way to pass the 10ects course. One can take the exam more than once (even if one has passed the course) to improve the final grade.
  • Date TBD
  • Anyone with demo class at least C has qualified to take the exam.
  • Exam (4 hours) consists 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 (and the end of Part 1)
  • 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