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