Master of Computer Application
Subject Name : Theory of Computation
Subject Code : 620007
• Understanding and development of theoretical models of computations and their analysis.
• The models of computations include (i) Finite Automata (and Regular Languages), (ii) Push Down Automata (and Context-free Languages), (iii) Turing Machine (and their Languages).
• The aim of analysis is to identify and prove the capabilities and limitations of particular models of Computations.
Knowledge of (a) Discrete Mathematics (b) Mathematical Induction and Structural Induction is desirable.
1. Introduction, Sets , Logic , Functions , Relations , Languages , Proofs Mathematical Induction , Strong Principle of Mathematical Induction , Recursive Definitions ,Structural Induction
2. Regular Languages & Regular Expressions, Finite Automata (FA), Distinguishing Strings w.r.t. Language , Union, Intersection, & Compliment of Languages