Syllabus Automata Theory - (2343114) Theory Term work Pract / Oral Total Internal Assessment End Sem Exam Exam Duration (in Hrs) IAT - I IAT - II IAT - I + IAT - II 20 20 40 60 02 - - - - 100 Sr. No. Module Detailed Content 0 Prerequisite Basic Mathematical Fundamentals : Sets, Logic, Relations, Functions. (Chapter - 1) I Introduction and Regular Languages Languages : Alphabets and Strings. Regular Languages : Regular Expressions, Regular Languages, Regular Grammars, RL and LL grammars, Closure properties Self-learning Topics : Practice exercise on Regular Expressions. Identify the tools also. (Chapter - 1) II Finite Automata Finite Automata : FA as language acceptor or verifier, NFA (with and without ε) , DFA, RE to NFA, NFA to DFA, Reduced DFA , NFA-DFA equivalence, FA to RE. Finite State Machines with output : Moore and Mealy machines. Moore and Mealy M/C conversion. Limitations of FA. Self-learning Topics : Practice exercise on FA and NFA. (Chapter - 2) III Context Free Grammars Context Free Languages : CFG, Leftmost and Rightmost derivations, Ambiguity, Simplification and Normalization (CNF & GNF) and Chomsky Hierarchy ( Types 0 to 3) Self-learning Topics : Practice numerical or exercise on CFG. (Chapter - 3) IV Push Down Automata Push Down Automata : Deterministic (single stack) PDA, Equivalence between PDA and CFG. Power and Limitations of PDA. Self-learning Topics : List the examples of PDA. (Chapter - 4) V Turing Machine Turing Machine : Deterministic TM, Variants of TM, Halting problem, Power of TM. Self-learning Topics : Practice numerical of TM. (Chapter - 5) VI Applications of Automata Applications of FA, CFG, PDA & TM. Introduction to Compiler & Its phases. Self-learning Topics : Case study on any one compiler. (Chapter - 6) Note : No questions will be asked in the end-semester exam from self-study topics. However, students are encouraged to explore these topics for a better understanding of the subject.
