Topics in Computability
TC lecture notes (
draft
)
Preface
Introduction
1
Notation
2
Proofs
3
Functions and cardinality
4
Words, languages, sets-of-languages
5
Operations on words
6
Operations on languages
7
Closure properties
8
More Exercises
Regular Languages
9
Finite Automata
10
Experiment with Finite Automata
11
Minimization of DFAs
12
Regular expressions
13
\mathbf{Regular}
– the set of all regular languages
14
Non-regularity
15
More Exercises
Context-Free Languages
16
Context-Free Grammars
17
Parsing and Ambiguity
18
Chomsky Normal Form and CFG depuration
19
Pushdown Automata
20
Experiment with CFGs and PDAs
21
Limitations of CFL
22
More Exercises
Topics in Computability
Topics in Complexity
References
Credits & Copyright
Topics in Computability
Warning
The content of this part is still under development and will be updated during the course.
22
More Exercises
Topics in Complexity