Mathematical Foundation for Computer Sciences (SE2324) (Automata Part.)

Spring Semester 2021

for undergraduates, school of software


Instructor

Guoqiang Li

Teaching Assistant

Ying Zhao: 765875306(AT) qq (DOT) com

Time

class of 2018:
10:00am - 11:40am, every Monday of odd weeks
10:00am - 11:40am, every Thursday

class of 2019:
10:00am - 11:40am, every Monday of even weeks
14:00pm - 15:40pm, every Thursday

Place

class of 2018:
312, Dong Shang Yuan

class of 2019:
311, Dong Shang Yuan

Office hour

Wed. 14:00-17:00 at 3203 Building of Software


References

[Sip12] Michael Sipser. Introduction to the Theory of Computation, 2012.

[Eid09] Abdulla Eid. Finite omega-Automata and Buchi Automata, lecture notes, 2009

[WDHR06] M. De Wulf, L. Doyen, T.A. Henzinger, and J.-F. Raskin. Antichains: A New Algorithm for Checking Universality of Finite Automata. CAV 2006

[DR10] Laurent Doyen and Jean-Francois Raskin. Antichain Algorithms for Finite Automata. CAV 2010

[Sch02] Stefan Schwoon. Model-Checking Pushdown Systems. PhD thesis 2002


Lectures

2018: Feb. 22
2019: Feb. 25
Lecture 1. Regular languages & DFA
[handout]

2018: Feb. 25
2019: Mar.  1
Lecture 2. Algorithms on FA
[handout]

2018: Mar.  4
2019: Mar.  4
Lecture 3. Automata on infinite objects
[handout]

2018: Mar.  8
2019: Mar. 11
Lecture 4. Efficient data structures and algorithms for FA
[handout]

2018: Mar. 11
2019: Mar. 15
Lecture 5. Context-free grammar
[handout]

2018: Mar. 18
2019: Mar. 18
Lecture 6. Algorithms on PDA
[handout]

2018: Mar. 22
2019: Mar. 25
Lecture 7. Pushdown systems
[handout]

2018: Mar. 25
2019: Mar. 29
Lecture 8. Conclusion
[handout]


Materials


Homework

Assignment 1. Exercises 1.5 (b, d); 1.6 (e, i); 1.11; 1.14 (b); 1.29; 1.38; 1.47; 1.48, deadline: Mar. 18
Assignment 2. Exercises 2.4 (b, c, d); 2.6 (a, d); 2.14; 2.18 (b); 2.20; 2.26, deadline: Apr. 8


Guoqiang Li
Last modified: Wednesday, Dec. 30, 2020.