Quick Links
Easy Studies
|
|
Theoretical Foundations of Computer Science |
UNIT I |
Propositions and Compound Propositions Logical Operations
Truth Tables Tautologies and Contradictions Logical Equivalence
Algebra of Propositions Conditional and Biconditional Statements
Arguments Logical Implication Quantifiers Negation of Quantified
Statements Basic Counting Principles Factorial Binomial
Coefficients Permutations Combinations Pigeonhole Principle
Ordered and Unordered Partitions. |
UNIT II |
Order and Inequalities Mathematical Induction Division
Algorithm Divisibility Euclidean Algorithm Fundamental
Theorem of Arithmetic Congruence Relation Congruence Equations
Semigroups Groups Subgroups Normal Subgroups
Homomorphisms Graph Theory: basic definitions-paths, reachability,
connectedness matrix representation of graphs, trees. |
UNIT III |
Finite Automata and Regular Expressions: Finite State Systems Basic
definitions Non-deterministic finite automata Finite automata with e-moves
Regular expressions. |
UNIT IV |
Properties of Regular sets: Pumping lemma Closure properties
Decision Algorithms My hill Nerode Theorem Context Free
Grammars Derivation Trees. |
UNIT V |
Simplifying Context free grammars - Chomsky normal forms
Greibach Normal forms Pushdown automata and context-free
languages. |
Text Books |
(i) J.P.Tremblay and R.Manohar, 1997, DiscreteMathematical Structures
with applications to Computer Science, Tata McGraw-Hill, New Delhi.
(ii) P.Linz, 1997, An Introduction to Formal Languages and Automata,
Second Edition, Narosa Pub. House, New Delhi.
(iii) S. Lipschutz and M. Lipson, 1999, Discrete Mathematics, Second Edition,
Tata McGraw-Hill, New Delhi.
(iv) J.E.Hopcraft and J.D.Ullman, 1993, Introduction to Automata Theory,
Languages and Computation, Narosa Publishing House, New Delhi. |
Reference Books |
(i) D.C.Kozen, 1997, Automata and Computability, Springer-Verlag, New York.
(ii) J. Martin, 2003, Introduction to Languages and the Theory of Computation,
3rd Edition, Tata McGraw-Hill, New Delhi. |
|
back |
|
|