Masters of Computer Applications:Theory of Computation

Thapar University
In Patiala

Price on request
You can also call the Study Centre
17523... More
Compare this course with other similar courses
See all

Important information

  • Master
  • Patiala
  • Duration:
    3 Years
Description

Important information
Venues

Where and when

Starts Location
On request
Patiala
Thapar University P.O Box 32, 147004, Punjab, India
See map

Frequent Asked Questions

· Requirements

Recognised Bachelors degree of minimum 3 years duration in any discipline with Mathematics at least at 10+2 school level and has also qualified in the Entrance Test to be conducted by the University.OR Recognised Bachelor's Degree of minimum 3 years duration in any discipline with Mathematics as one of the subjects and has also qualified in the Entrance Test to be conducted by the University.

Course programme

Semester I

Discrete Mathematical Structures
Elements of Electronics Engineering
Problem Solving and Programming in C
Operating Systems
Computer Organization and Architecture


Semester II

Data Structures
Fundamental of Microprocessors and Interfacing
Object Oriented Programming using c++ and Java
System Analysis and Design
Statistics and Combinatorics


Semester III

Software Engineering
Data Base Management System
Design and Analysis of Algorithms
Operations Research
Computer Networks


Semester IV

Advanced Java and Network Programming
Computer Graphics and Multimedia
ERP and Tools
Minor Project


Semester V

Information and Network Security
Software Project Management
Net Framework and C# Programming


Semester VI

System Development Project



Theory of Computation

Recursive Languages: Recursive Definition, Alphabets, Language, Regular Expression, definitions of Finite State Machine, Transition Graphs, Deterministic & Non-deterministic Finite State Machines, Regular Grammar, Left-Linear and Right Linear, Thomson’s Construction to Convert Regular Expression to NDFA & Subset Algorithm to convert NDFA to DFA. Minimization of DFA, Finite State Machine with output (Moore machine and Melay Machine), Conversion of Moore machine to Melay Machine & Vice-Versa.

Properties of Regular languages: Conversion of DFA to Regular Expression, Pumping Lemma, Properties and Limitations of Finite state machine, Decision Properties of Regular Languages, Application of Finite Automata.

Context Free Grammar and PDA: Context Free Grammar, Writing Context free Grammar for Problems, Derivation tree and Ambiguity, Application of Context free Grammars, Chomsky and Greibach Normal form, Conversion of CFG to CNF and GNF. Properties of context free grammar, CYK Algorithm, Decidable properties of Context free Grammar, Pumping Lemma for Context free grammar, Push down Stack Machine, Design of Deterministic and Non-deterministic Push-down stack, Parser Design.

Turing Machine: Turing machine definition and design of Turing Machine, Church-Turing Thesis, Variations of Turing Machines, Combining Turing machine, Universal Turing Machine, Post Machine, Chomsky Hierarchy.

Incommutability: Halting Problem, Turing Enumerability, Turing Acceptability and Turing Decidabilities. Unsolvable problems about Turing machines.

Computation Complexity: P, NP and NP Complete Problems.


Compare this course with other similar courses
See all