# Theory of Computation (2160704)

## Teaching Scheme (in Hours)

Theory Tutorial Practical Total
3 0 0 3

Subject Credit :  3

Theory
ESE (E)
Theory
PA (M)
Practical
ESE Viva (V)
Practical
PA (I)
Total
70 30 0 0 100

## Syllabus Content

###### Unit-1:  Review of Mathematical Theory

Sets, Functions, Logical statements, Proofs, relations, languages, Mathematical induction, strong principle, Recursive definitions

###### Unit-2:  Regular Languages and Finite Automata

Regular expressions, regular languages, applications, Automata with output-Moore machine, Mealy machine, Finite automata, memory requirement in a recognizer, definition, union, intersection and complement of regular languages.Non Determinism Finite Automata, Conversion from NFA to FA, ?- Non Determinism Finite Automata Conversion of NFA- ? to NFA and equivalence of three Kleene’s Theorem, Minimization of Finite automata Regular And Non Regular Languages – pumping lemma.

###### Unit-3:  Context free grammar (CFG)

Definition, Unions Concatenations And Kleen’s of Context free language Regular grammar, Derivations and Languages, Relationship between derivation and derivation trees, Ambiguity Unambiguous CFG and Algebraic Expressions BacosNaur Form (BNF), Normal Form – CNF

###### Unit-4:  Pushdown Automata, CFL And NCFL

Definition, deterministic PDA, Equivalence of CFG and PDA, Pumping lemma for CFL, Intersections and Complements of CFL, Non-CFL

###### Unit-5:  Turing Machine (TM)

TM Definition, Model Of Computation And Church Turning Thesis, computing functions with TM, Combining TM, Variations Of TM, Non Deterministic TM, Universal TM, Recursively and Enumerable Languages, Context sensitive languages and Chomsky hierarchy

###### Unit-6:  Computable Functions

Partial, total, constant functions, Primitive Recursive Functions, Bounded Mineralization, Regular function, Recursive Functions

## Reference Books

Sr. Title Author Publication Amazon Link
1 An introduction to automata theory and formal languages Adesh K. Pandey S.K. Kataria& Sons
2 Introduction to computer theory Deniel I. Cohen Joh Wiley & Sons
3 Computation: Finite and Infinite Marvin L. Minsky Prentice-Hall
4 Compiler Design Alfred V Aho Addison Weslley
5 Introduction to the Theory of Computation Michael Sipser
6 Automata Theory, Languages, and Computation John Hopcroft, Rajeev Motowani, and Jeffrey Ullman

### BE (CE) ⇒ Semester: 6

Darshan Institute of Engineering & Technology is a leading institute offering undergraduate (B.E.), postgraduate (M.E.) and Diploma programs in engineering.

## Our Contacts

At Hadala, Rajkot - Morbi Highway,
Gujarat-363650, INDIA

(+91) 97277 47310
(+91) 97277 47311