MNIT Jaipur Syllabus computer science Theory of Computation


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.

Text/ References:

1. Hopcroft, Motwani and Ullman: Introduction to Automata Theory, Languages and Computation,

Pearson Education.

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.

Leave a Comment