AFL course syllabus

 

Autumn semester 2024
Automata and Formal Languages

 

The course has two parts:

  • Part 1 on Sep 3 – Oct 17,
  • Part 2 on Oct 28 – Dec 12.

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

 

Lectures:

  • 10:15-12:00 Tuesdays in room M1 (Quantum, 2nd 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/afl2024

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 (week of Oct 21-25, date TBD)
  • 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. Dates TBD. The first midterm exam is the same as the final exam of the 5ects course.
  • 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