UNIT I

FINITE AUTOMATA: Introduction, Deterministic Finite Automata (DFA) -Formal definition, simpler notations (state transition diagram, transition table), language of a DFA. Non-deterministic Finite Automata (NFA)- Definition of NFA, language of an NFA, Equivalence of Deterministic and Non-deterministic Finite Automata, Applications of Finite Automata, Finite Automata with Epsilon Transitions, Eliminating Epsilon transitions, Minimization of Deterministic Finite Automata, Finite automata with output and Inter conversion.

UNIT II

REGULAR EXPRESSIONS: Introduction, Identities of Regular Expressions, Finite Automata and Regular Expressions- Converting from DFA᎙s to Regular Expressions, Converting Regular Expressions to Automata, applications of Regular Expressions. REGULAR GRAMMARS: Definition, regular grammars and FA, FA for regular grammar, Regular grammar for FA. Proving languages to be non-regular -Pumping lemma, applications, Closure properties of regular languages.

UNIT III

 CONTEXT FREE GRAMMER (CFG): Derivation Trees, Sentential Forms, Rightmost and Left most derivations of Strings. Ambiguity in CFG᎙s, Minimization of CFG᎙s, CNF, GNF, Pumping Lemma for CFL᎙s, Enumeration of Properties of CFL.

UNIT IV

PUSHDOWN AUTOMATA: Definition, Model, Acceptance of CFL, Acceptance by Final State and Acceptance by Empty stack and its Equivalence, Equivalence of CFG and PDA.TURING MACHINES (TM): Formal definition and behavior, Languages of a TM, TM as accepters, and TM as a computer of integer functions, Types of TMs.

UNIT V

RECURSIVE AND RECURSIVELY ENUMERABLE LANGUAGES (REL): Properties of Recursive and recursively enumerable languages, Universal Turing machine, The Halting problem, Undecidable problems about TMs. Context sensitive language and linear bounded automata (LBA), Chomsky hierarchy, Decidability, Post’s correspondence problem (PCP), undecidability of PCP.

TEXT(S)

1. John Hopcroft, Rajeev Motwani, Jeffrey D. Ullman, ᎜Introduction to Automata Theory Languages and Computation᎝, 3^rd Edition, Pearson Education, India, 2007.

REFERENCE MATERIALS

1. L. P Mishra, N. Chandrashekaran, ᎜Theory of Computer Science-Automata Languages and Computation ᎜, 2nd edition, Prentice Hall of India, India,2003.

2. Zohar Manna and Richard Waldinger ᎜The Logic of Computer Programming᎝, SRI International, 2013.

E-RESOURCES

1. tutorialspoint.com Ꮊ automata theory

2. www.quora.com/logicandcomputation