Formal Languages and Automata Theory

A. Course Objective: Formal languages and automata theory is a central course in the field of computer science. It deals with the formalism of machines and helps to understand some intrinsic question about machines. A famous question was asked long back: Since the power of our machine is increasing day by day, can we solve all problems with this powerful machine. One such problem is Hilbert's 10th problem. To show a problem is solvable by a machine requires one to design an algorithm. But to show that no machines can solve a problem requires one to formalize the abstraction of machine. This course helps the students to identify such beautiful problems and make them understand the inherent limitation of machines.

B. Course Instructor: Dr. Avijit Dutta (Session: 2021-22, IAI, TCG CREST)

C. Topics Covered:

0. Preliminaries: Alphabets, Strings, Languages, Finite Set, Countably infinite set, Uncountable infinite set

1. Introduction to Finite State Machines: Deterministic Finite Automata, Non-deterministic finite automata, Equivalence of DFA and NFA, Regular Language, Regular Expression, Closure Properties of Regular Languages, Pumping Lemma for Regular Languages, Myhill-Nerode Theorem, Minimization of DFA, Elementary questions about regular languages

2. Regular and Context Free Grammars: Regular Grammar, Right and Left Linear Grammar, Equivalence of Regular Language and Regular Grammar, Context Free Grammar, Leftmost and rightmost derivation, Derivation Trees, Parsing and Ambiguity, Transformation of Context Free Grammars, Chomsky Normal Form, Greibach Normal Form,  Context Free Languages, Membership Algorithm for Context Free Grammar, Deterministic Context Free Grammar 

3. Pushdown Automata: Non-deterministic Pushdown Automata, Pushdown Automata and Context Free Languages, Deterninistic Pushdown Automata, Non-equivalence between NPDA and DPDA, Deterministic CFL,

4. Properties of Context Free Languages: Pumping Lemma for CFL, Pumping Lemma for Linear Languages, Closure Properties of Context Free Languages, Decidable Properties of Context Free Languages

5. Turing Machines: Turing Machine and Its variants (multi-tape, multi-dimensional, turing machine with stay option, offline turing machine, turing machine with semi-infinite tape, non-deterministic turing machine etc.), Universal Turing Machine, Turing Machine as a transducer, Turing Machine as a language accepter, Linear Bounded Automata,

6. Hierarchy of Languages and Computability: Recursive Language, Recursive Enumerable Languages, Rice's Theorem, Halting Problem, Computability and Decidability, Reduction of one undecidable problem to another,  Undecidable problems for CFL, Post Correspondence Problems.

D. References

1. An Introduction to Formal Languages and Automata by Peterlinz (5th Edition)
2. Introduction to the Theory of Computation by Michael Sipser (3rd Edition)
3. Introduction to Automata Theory, Languages and Computation by J.E.Hopcroft and J.D.Ullman 
4. Elements of The Theory of Computation by H. R. Lewis and C. H. Papadimitriou
5. Introduction to Automata Theory, Languages and Computation by J. E. Hopcroft, J. D. Ullman and R. Motwani: 

E. Resources

All the board works of the course can be found here