Theory of Computation

GANPAT UNIVERSITY 

FACULTY OF ENGINEERING & TECHNOLOGY

Programme

Bachelor of Technology

Branch/Spec.

Computer Science & Engineering

(CBA/ /BDA/CS)

Semester

VI

Version

1.1.1.1

Effective from Academic Year

2022– 23

Effective for the batch Admitted in

June 2020

Subject  code

2CSE601

Subject Name

Theory of Computation                                                               

Teaching scheme 

Examination scheme (Marks)

(Per week)

Lecture

(DT)

Practical

(Lab.)

Total

CE

SEE

Total

L

TU

P

TW

Credit 

3

1

0

0

4

Theory 

40

60

100

Hours

3

1

0

0

4

Practical

00

00

00

Pre-requisites:

Engineering Mathematics, Data structures and Algorithms

Learning Outcome:

After learning the course, the students should be able to:

• Introduce the mathematical foundations of computation including automata theory.
• Differentiate and give examples for the different types of automata like finite automata, push down automata, linear bounded automata and Turing machine.  
• Correlate the different types of automata to real world applications.
• Choose and design appropriate automata for the different requirements outlined by theoretical computer science.

Theory syllabus

Unit

Content

Hrs

1

Review of Mathematical Background 

Sets, Functions, Logical statements, Proofs, Relations, Languages, The Principle of Mathematical induction, Recursive definitions.

3

2

Regular Languages and Finite Automata

Regular expressions, Regular languages, Memory required to recognize a language, Finite automata, Distinguishable strings, Union, intersection and complement of regular languages, Automata with output-Moore machine, Mealy machine.

8

3

Nondeterminism and Kleen’s Theorem

Non-deterministic finite automata, non-deterministic finite automata with ^ transitions, Kleen's theorem- Part-1

8

4

Regular and Non-Regular Language

Minimization of Finite automata, non-regular and regular languages, Pumping Lemma, Decision problems and decision algorithms, regular languages in relation to programming languages

8

5

Context-Free/Non-Context Free Languages and Push-Down Automata

Context-free languages, Regular Grammars, Derivation tree and ambiguity, An Unambiguous CFG, Simplified and Normal forms, Chomsky normal form, Chomsky Classification of Grammars.

6

6

Pushdown Automata and CFL

Push -Down Automata, Deterministic PDA, Types of acceptances and their equivalence, Equivalence of CFG and PDA, parsing, Non-CFL and CFL, Pumping Lemma for CFL, Intersection and Complement of CFL

8

7

Turing Machine

Models of computation, Combining TMs, Computing a function with TMs. Variations on Turing Machines, doubly infinite and more than one Tapes, Non-deterministic and Universal TM

5

Self-Study

Non-deterministic and Universal Turing Machine

Mooc Course

Course Name: Theory of Computation

Link: https://nptel.ac.in/courses/106/106/106106049/

Text Books

1

Introduction to Languages and Theory of Computation: By John C. Martin

Reference Books

1

Computation: Finite and Infinite: By Marvin L. Minsky, Prentice-Hall 

2

Introduction to formal languages: By G. E. Reevsz, Mc-graw hill

3

Introduction to Formal Language Theory: By M.H. Harrison

Course Outcomes:

COs

Description

CO1

Introduce the mathematical foundations of computation including automata theory

CO2

Differentiate and give examples for the different types of automata like finite automata, push down automata, linear bounded automata and Turing machine

CO3

Correlate the different types of automata to real world applications

CO4

Choose and design appropriate automata for the different requirements outlined by theoretical computer science

Mapping of CO and PO: