Posts

Showing posts from 2009

GTU Syllabus for Theory of Computation

GUJARAT TECHNOLOGICAL UNIVERSITY
Master of Computer Application

Subject Name : Theory of Computation
Subject Code : 620007

Objectives:
• 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.

Prerequisites:
Knowledge of (a) Discrete Mathematics (b) Mathematical Induction and Structural Induction is desirable.

Contents:

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

3…