Course Code- CS403
(3-CREDIT) (L-T-P/3-1-0)

Module I: Fundamentals & Finite Automata:
Alphabet, Strings, Language, Operations, Mathematical proving techniques, Finite state machine,
definitions, finite automaton model, acceptance of strings, and languages, Deterministic Finite
Automaton (DFA) and Non deterministic Finite Automaton (NFA), transition diagrams and
Language recognizers. Equivalence of DFA and NFA, NFA to DFA conversion, NFA with ɛ -
transitions - Significance, acceptance of languages. Equivalence between NFA with and without ɛ -
transitions, minimization of FSM, Finite Automata with output- Moore and Mealy machines and
conversion of Mealy to Moore and vice-versa.
Module II: Regular Expression and Languages:
Regular sets, regular expressions, identity rules, Constructing finite Automata for a given regular
expressions, Conversion of Finite Automata to Regular expressions. Regular grammars-right linear
and left linear grammars, conversion of right linear grammar to left linear and vice-versa,
equivalence between regular grammar, regular expression and FA, Pumping lemma of regular sets,
closure properties of regular sets.
Module III: Context Free Grammars and Push Down Automata:
Context free grammar, derivation trees, sentential forms. Right most and leftmost derivation of
strings. Ambiguity in context free grammars. Reduction of Context Free Grammars. Chomsky
normal form(CNF), Greiback normal form(GNF), Pumping Lemma for Context Free Languages.
Simplification of CFL.
Push down automata(PDA) definition, model, acceptance of CFL, Acceptance by final state and
acceptance by empty state and its equivalence. Equivalence of CFG and PDA, interconversion.
Introduction to DCFL and DPDA. DPDA Vs NPDA.
Module IV: Turing Machine:
Turing Machine definition, representation of Turing Machines model, Variants of TM, design of TM,
linear bounded automata,
Module V: Computational Complexity & Decidability, Recursively Enumerable Languages:

Complexity : Growth rate of a function, class P and NP, polynomial time reduction and NP-
Completeness, NP-Complete problems(SAT, CSAT,Hamiltonian circuit, travelling salesman, vertex

cover). Decidability: decidability, decidable language, undecidable language, halting problem of
Turing Machine.Computability: primitive recursive function and recursive function.
TEXT BOOKS:
1. Theory of Computer Science (Automata Language and Computation) K.L.P. Mishra and N.
Chandrasekran, PHI.
2. Introduction to Automata Theory, Language and Computation, John E, Hopcropt and Jeffery
D. Ullman, Narosa Publishing House.
REFERENCE BOOKS:
1. Theory of Automata and Formal Language, R.B. Patel & P. Nath, Umesh Publication.
2. An Introduction and Finite Automata Theory, Adesh K. Pandey, TMH.
3. Theory of Computation AM Natrajan, Tamilarasi, Bilasubramani, New Age International
Publishers, Chhattisgarh Swami Vivekan.
4. An introduction to Formal Languages and Automata by Peter Linz, Narosa Publ