Masters of Computer Applications:Theory of Computation

Master

In Patiala

Price on request

Description

  • Type

    Master

  • Location

    Patiala

  • Duration

    3 Years

Facilities

Location

Start date

Patiala (Punjab)
See map
Thapar University P.O Box 32, 147004

Start date

On request

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.

Questions & Answers

Add your question

Our advisors and other users will be able to reply to you

Who would you like to address this question to?

Fill in your details to get a reply

We will only publish your name and question

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

Price on request