Automata

Syllabus:

Regular expressions and finite automata. Context-free grammars and push-down automata. Regular and contex-free languages, pumping lemma. Turing machines and undecidability.

1. What Books to read :

Book Name :

1 Peter Linz - An Introduction to Formal Languages and Automata : 3rd edition , chapter 1 to 12

2 Daniel I A Cohen - Introduction to Computer Theory , chapter 1 to 31

3 John C Martin - Introduction to Languages and The Theory of Computation : 4th Edition , chapter - 1 to 9

Video : NPTEL IITK - https://www.youtube.com/playlist?list=PLbMVogVj5nJSd25WnSU144ZyGmsqjuKr3

Sai Simonson - https://www.youtube.com/playlist?list=PL601FC994BDD963E4

2. What To read : Topics for that subject to read along with Chapter Subparts : ** marked parts are important for problems

**1 Regular expressions Linz Chapter - 3 - 3.1, 3.2, 3.3 / Cohen - Chapter : 3 , 4 / Martin - 3.1 to 3.5

**2 finite automata Linz Chapter - 2- 2.1, 2.2, 2.3,2.4 / Cohen - Chapter : 5, 6, 7, 8, 9 / Martin - 2.1 to 2.6

**3 Context-free grammars Linz Chapter - 5 : 5.1 , 5.2, 5.3 , Chapter 6 - 6.1, 6.2 / Cohen - Chapter : 13 ,14,15,16 / Martin : 4.2

** 4 push-down automata Linz Chapter - 7 : 7.1, 7.2, 7.3 / Cohen - Chapter : 17 and Chapter : 18 / Martin : 5.1 to 5.5

**5 Regular Language Linz Chapter - 4 : 4.1, 4.2, 4.3 / Cohen - Chapter : 10 , 11, 12 / Martin : 3.1, 4.3

6 contex-free languages Linz Chapter - 8.2 / Cohen - Chapter : 19 , Chapter : 21 , 22, 23 / Martin 4.1, 4.2, 4.4, 4.5

7 pumping lemma Linz Chapter - 8.1 / Cohen - Chapter : 20 / Martin - 6.1 to 6.3

** 8 Turing machines Linz Chapter - 9 : 9.1 , 9.2, 9.3 , Chapter 10 , chapter 11 / Cohen - Chapter : 24, 25, 26 , 27 / Martin 7.1 to 7.8 , 8.1 to 8.5

9 undecidability Linz Chapter - 12 : 12.1 to 12.4 / Cohen - Chapter : 28, 29, 30, 31 / Martin 9.1 to 9.5

3. Types of problems from where questions came previous years :
RE and FA

Finite Automata covers approximately 50% questions from TOC. So give it more time then others.

• Minimization of finite Automata , Closure Properties of finite automata .

• Finding minimum number of states, NFA to DFA conversion, Finding Regular Expressions, mealy moore machine .

• Regular Expression identification.

• Construction of finite Automata from regular Expression

• Generation of regular expression from finite Automata

• Equivalence of regular Expression

CFG and PDA

• In Context free grammer practice more on simplification of CFG, pushdown automata, closure properties etc.

Regular and Context Free Languages

• closure properties of regular language

• Decidability of regular Language

• Whether the given language is regular or not

• Do problems on finding category of any language or grammar.

• Concepts related to expressive power of different languages.

Turing Machine and Undecidability

• Basic problems related to NP-Completeness. Properties of Recursive and Recursive Enumerable Languages.

• Turing Machine making and expressive power of different type of turing machine. (also useful for interview ) .