Formal languages and automata theory Slides

Topic
Click to Download PPT
Tutorial
1
Introduction, finite automata
2
Nondeterministic finite automata
3
Regular expressions
4
Properties of regular languages
5
Limitations of finite automata
6
DFA minimization
7
More on DFA minimization and equivalence
8
Context-free languages, parsing
9
Normal forms, parsing algorithms
10
Pushdown automata
11
Limitations of PDAs
12
Parsers for programming languages
13
Midterm review
Midterm exam
14
LR(k) parsers
15
The Church-Turing thesis
16
Variants of Turing Machines
17
Undecidability
18
More undecidable problems
19
Undecidable problems about CFGs
20
Efficient Turing Machines
21
Polynomial time, P and NP
22
Reductions, the Cook-Levin Theorem
23
NP-complete problems
24
Interaction and zero-knowledge

No comments: