Masters of Computer Applications:Theory of Computation
Master
In Patiala
Description
-
Type
Master
-
Location
Patiala
-
Duration
3 Years
Facilities
Location
Start date
Start date
About this course
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.
Reviews
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.
Masters of Computer Applications:Theory of Computation