**GUJARAT TECHNOLOGICAL UNIVERSITY**

Master of Computer Application

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. Non-deterministic Finite Automata (NFA), NFA with Null-Transitions, Kleene's Theorem

4. A Criterion for Regularity, Minimal Finite Automata, Pumping Lemma for Regular Languages

5. Introduction to Context-Free Grammar (CFG) , Regular Grammars , Derivation (Parse) Trees & Ambiguities , An Unambiguous CFG for Algebraic Expressions , Simplified

Forms & Chomsky Normal Forms

6. Introduction to Push Down Automata (PDA), Deterministic PDA (DPDA), PDA corresponding to a Given CFG , CFG Corresponding to a Given PDA , Parsing

7. The Pumping Lemma for CFG , Intersection & Complement of CFGs , Decision Problems Involving CFGs

8. Turing Machine (TM) Definition & Examples, Computing a Partial Function with a TM

9. Recursive Enumerable & Recursive Languages, Enumerating a Language, Context-Sensitive Languages & Chomsky Hierarchy

**Note:**

1. Only those proofs which use Induction are included in the syllabus. In case of other theorems and Lemmas, proof may be omitted. However, the purpose, importance and applications of all theorems and Lemmas must be discussed.

**Main Reference Book:**

"Introduction to Languages and the Theory of Computation", John C. Martin, Tata McGraw-Hill, (2003), 3rd Edition, ISBN: 007049939X

**Suggested Additional Reading:**

1. "Elements of the Theory of Computation", Harry Lewis & Christos H. Papadimitriou,IEEE (PHI), 2nd Edition ,ISBN-978-81-203-2233-2.

2. " Theory of Computation”, Michael Sipser, ", Cengage Learning(2007), ISBN-13: 978-81-315-0513-7

3. “ Introduction to Automata Theory, Languages, and Computation ”, Hopcroft, Motwani & Ullman, Pearson Education, 3rd Edition, (2008), ISBN: 978-81-317-2047-9

**Chapterwise Coverage from main reference book(s) :**

Chapters : 1.1-1.5, 2.1-2.5, 3.1-3.5, 4.1-4.3, 5.1-5.3, 6.1-6.6, 7.1-7.6, 8.1-8.3,9.1-9.2, 10.1-10.2,10.4.

**Accomplishment of Students after Studying this Course :**

• Ability to distinguish between Regular Expressions and Non-regular Expressions.

• Ability to develop FA for a given regular language and vice versa (i.e. to develop a regular language from a given FA).

• Ability to use Pumping Lemma to optimize FA.

• Understanding of CFG with its potential to describe a big set of non-regular languages using finite number of production rules.

• Ability to develop Push Down Automata for a given CFG.

• Understanding of Turing Machine and their languages, with a good feel of the enhanced and bigger set of languages supported by Turing Machine.