Unit-I
Relation: Type and compositions of relations, Pictorial representation of relations, Closures of relations, Equivalence relations, Partial ordering relation.
Function: Types, Composition of function, Recursively defined function
Mathematical Induction: Piano’s axioms, Mathematical Induction
Discrete Numeric Functions and Generating functions
Simple Recurrence relation with constant coefficients, Linear recurrence relation without constant coefficients, Asymptotic Behavior of functions
Algebraic Structures: Properties, Semi group, Monoid, Group, Abelian group, properties of group, Subgroup, Cyclic group, Cosets, Permutation groups, Homomorphism, Isomorphism and Automorphism of groups.
Unit –II
Propositional Logic: Preposition, First order logic, Basic logical operations, Tautologies, Contradictions, Algebra of Proposition, Logical implication, Logical equivalence, Normal forms, Inference Theory, Predicates and quantifiers, Posets, Hasse Diagram, Lattices: Introduction, Ordered set, Hasse diagram of partially ordered set, Consistent enumeration, Isomorphic ordered set, Well ordered set, Lattices, Properties of lattices, Bounded lattices, Distributive lattices, and Complemented lattices.
Unit-III
Introduction to defining language, Kleene Closure, Arithmetic expressions, Chomsky Hierarchy, Regular expressions, Generalized Transition graph.
Unit-IV
Conversion of regular expression to Finite Automata, NFA, DFA, Conversion of NFA to DFA, Optimizing DFA, FA with output: Moore machine, Mealy machine, Conversions.
Unit-V
Non-regular language: Pumping Lemma, Myhill Nerode Theorem, Pushdown Automata, and Introduction to Turing Machine and its elementary applications to recognition of a language and computation of functions.
References
Liptschutz, Seymour, “Discrete Mathematics”, TMH
Trembley, J.P & R. Manohar, “Discrete Mathematical Structure with Application to Computer Science”, TMH
Kenneth H. Rosen, ” Discrete Mathematics and its applications”, TMH
Doerr Alan & Levasseur Kenneth, “Applied Discrete Structures for Computer Science”, Galgotia Pub. Pvt. Ltd
Gersting,“Mathematical Structure for Computer Science”,WH Freeman & Macmillan
6. Kumar Rajendra, “Theory of Automata: Languages and Computation”, PPM
7. Hopcroft J.E, Ullman J.D., “Introduction to Automata theory, Languages and
Computation”, Narosa Publishing House, New Delhi
8. C.L.Liu, “Elements of Discrete Mathematics”, McGraw Hill”
9. Peter Grossman, “Discrete Mathematics for Computer”, Palgrave Macmillan