Introduction, Deterministic Finite Automata (DFA) -Formal definition,simpler notations (state transition diagram, transition table), language of a DFA. NondeterministicFinite Automata (NFA)- Definition of NFA, language of an NFA, Equivalence of Deterministic andNondeterministic Finite Automata, Applications of Finite Automata, Finite Automata with EpsilonTransitions, Eliminating Epsilon transitions, Minimization of Deterministic Finite Automata, Finiteautomata with output and Inter conversion.
Introduction, Identities of Regular Expressions, Finite Automataand Regular Expressions- Converting from DFA’s to Regular Expressions, Converting RegularExpressions to Automata, applications of Regular Expressions.REGULAR GRAMMARS: Definition, regular grammars and FA, FA for regular grammar, Regulargrammar for FA. Proving languages to be non-regular -Pumping lemma, applications, Closureproperties of regular languages.
CONTEXT FREE GRAMMER (CFG):
Derivation Trees, Sentential Forms, Rightmost and Leftmostderivations of Strings. Ambiguity in CFG’s, Minimization of CFG’s, CNF, GNF, Pumping Lemma forCFL’s, Enumeration of Properties of CFL.
Definition, Model, Acceptance of CFL, Acceptance by Final State andAcceptance by Empty stack and its Equivalence, Equivalence of CFG and PDA.TURING MACHINES (TM): Formal definition and behaviour, Languages of a TM, TM as accepters,and TM as a computer of integer functions, Types of TMs.
RECURSIVE AND RECURSIVELY ENUMERABLE LANGUAGES (REL):
Properties of recursiveand recursively enumerable languages, Universal Turing machine, The Halting problem, Undecidableproblems about TMs. Context sensitive language and linear bounded automata (LBA), Chomskyhierarchy, Decidability, Post's correspondence problem (PCP), undecidability of PCP.
Reference Book:
1. K. L. P Mishra, N. Chandrashekaran,“ Theory of Computer Science-AutomataLanguages and Computation “, 2nd edition, Prentice Hall of India, India,2003.
2.Zohar Manna and Richard Waldinger “ The Logic of Computer Programming”, SRI International, 2013.
Text Book:
1. John E. Hopcroft, Rajeev Motwani, Jeffrey D. Ullman ,“ Introduction to Automata TheoryLanguagesandComputation”, 3rd Edition, Pearson Education, India, 2007.
