Theory of Computing
Table of Contents
In this course we will take a look at various formal computing models. They enable us to classify languages based on their "difficulty". We will also see how the theory is applied to various fields like compiler design.
1. Administrivia
The lectures will be on J1 and J2 slots in hall 10/201. The tutorial will be on I2 in hall 1/102.
2. Lectures
2.1. Mar 05
Definition of PDA.
2.2. Mar 01
Grammar for arithmetic expressions. Associativity and precedence handling.
2.3. Feb 28
Ambiguity in context-free grammars.
2.4. Feb 27
Context-free grammars. Derivations.
2.5. Feb 16
Problem solving session on regular languages.
2.6. Feb 13
Problem solving session on regular languages.
2.7. Feb 09
Revision on proof writing.
2.8. Feb 06
Pumping lemma and proving non-regularity.
2.9. Feb 02
NFAs to regular expressions through GNFAs.
2.10. Jan 30
Regular expressions to NFAs.
2.11. Jan 23
Regular expressions.
2.12. Jan 19
Converting NFA to DFA (subset construction).
2.13. Jan 16
Formal definition of NFA. NFA construction for union, concatenation, Kleene star.
2.14. Jan 9
Closure of regular languages under union. Concatenation of languages. NFA.
2.15. Jan 5
DFA.
2.16. Jan 3
Overview of the course. Finite automata.
3. References
- "Introduction to Theory of Computation", Michael Sipser, 3rd edition.
- Google classroom for announcements