MNIT Jaipur Syllabus computer science Theory of Computation
Theory of Computation
Introduction to automata theory, formal languages, recursive definitions, regular expressions, finite
automata, transition graphs and Kleen’s theorem.
Non-determination, finite automata with output, regular languages, minimization of finite automata,
pumping lemma for regular languages.
Chomsky classification of languages, regular grammars, context free grammars, simplification of context
free grammars, Normal forms of context free grammars.
Push Down Automata Theory: push down automata and languages, push down automata and context free
grammars, pumping lemma for context free languages.
Turing hypothesis, Turing machine, Minskey’s theorem, TM variation and encoding, Post machines,
computability and acceptability.
Elements of prepositional logic and predicate calculus.
1. Hopcroft, Motwani and Ullman: Introduction to Automata Theory, Languages and Computation,
2. Cohen: Introduction to Computer Theory, Addison Wesley.
3. Martin: Introduction to Languages and Theory of Computation, TMH.
4. Papadimitriou, Introduction to Theory of Computing, Prentice Hall.
5. K.Krishnamurthy: Theory of Computation.CP-252 DBMS Lab (0-0-3) 2
The following proposed coverage are broad guiding areas lab. The instructor offering the course in
consultation with the theory offered can adopt further variations in tune with CP-222.
1. Conceptual designs using ER diagrams.
2. Design of databases. Based on templates, files and relational basis.
3. Development and implementation of DB system from the fundamentals.
4. Experiments on SQL queries.