Theory of Automata

Course Description:

The course introduces some fundamental concepts in automata theory and formal

languages including grammar, finite automaton, regular expression, formal language, pushdown automaton, and Turing machine. Not only do they form basic models of computation, they are also the foundation of many branches of computer science, e.g. compilers, software engineering, concurrent systems, etc. The properties of these models will be studied and various rigorous techniques for analyzing and comparing them will be discussed, by using both formalism and examples.

Lecture Slides:

1. 01 Introduction
   
2. 02 Regular Expression
3. 03 Finite Automata
4. 04 Finite automata Examples
5. 05 Finite Automata Examples
6. 06 Non-Determinism
7. 07 GTG and Theorem
8. 08 Union and concatenation of two FAs
9. 09 FA with output
10. 10 Examples of Mealy Machine
11. 11 Concatenation and Intersection of FAs
12. 12 Pumping Lemma for Regular Languages
13. 13 CFG Introduction
14. 14 CFG Examples
15. 14a CFG Solutions 1
16. 14b CFG Solutions 2
17. 15 Chomsky Normal Form
18. 15b Chomsky Normal Form (New)
19. 18 Push Down Automata
20. 19 Properties of CFL (New)
21. 19 Turing Machine
22. 20 Turing Machine Examples 1
23. 21 Turing Machine Examples 2
24. 22 Decidability and UnDecidability

Assignments:

1. Assignment No 01
   
2. Assignment No 02
   
3. Assignment No 03
   
4. Assignment No 04
5. Assignment No 05

Recommended Book :

Introduction to Computer Theory By Cohen

Introduction to Theory of Computation by Michel Sipser