19CSC53 THEORY OF COMPUTATION SEMESTER: V
PRE-REQUISITES: NIL Category: PC
L T P C
COURSE OBJECTIVES: 3 1 0 4
To construct automata for any given pattern and find its equivalent
regular expressions
To design CFG for any given language
To understand the need for Turing machines and their capability
To understand undecidable problems and NP problems
Upon completion of this course, the students will be familiar with,
Regular languages and Finite Automata
Context Free Languages and Push Down Automata
Turing Machines
Recursively and Recursively Enumerable Languages
Undecidable problems.
UNIT – I : REGULAR LANGUAGES (9+3 Periods)
Introduction- Basic Mathematical Notation and techniques- Finite State systems – Basic Definitions – Finite
Automaton – DFA & NDFA – Finite Automaton with €- moves – Regular Languages- Regular Expression
– Equivalence of NFA and DFA – Equivalence of NDFA‟s with and without €-moves – Equivalence of
finite Automaton and regular expressions –Minimization of DFA- - Pumping Lemma for Regular sets –
Problems based on Pumping Lemma.
Regular Languages and Regular Expressions - Memory Required to Recognize a Language -Finite
Automata - Distinguishing One String from Another - Unions, Intersections, and Complements.
Nondeterministic Finite Automata - Nondeterministic Finite Automata with ˄-transitions -Kleene’s
Theorem. Criterion for Regularity- Minimal Finite Automata-Pumping Lemma for Regular Languages
UNIT – II : CONTEXT FREE LANGUAGES (9+3 Periods)
Grammar Introduction– Types of Grammar - Context Free Grammars(CFG) and Languages– Derivations
and Languages – Ambiguity- Relationship between derivation and derivation trees – Simplification of CFG
– Elimination of Useless symbols - Unit productions - Null productions – Greiback Normal form –
Chomsky normal form – Problems related to CNF and GNF.
Pushdown Automata- Definitions – Moves – Instantaneous descriptions – Deterministic pushdown
automata – Equivalence of Pushdown automata and CFL - pumping lemma for CFL – problems based on
pumping Lemma.
Context-Free Grammar (CFG) – Derivation Trees – Ambiguity in Grammars and Languages –
Equivalence of Parse Trees and Derivation – Simplification of Context-free Grammar – Chomsky Normal
Form – Greibach Normal Form - Definition of the Pushdown Automata – Languages of a Pushdown
Automata – Equivalence of Pushdown Automata and CFG– Pumping Lemma for CFL – Closure
Properties - Deterministic Pushdown Automata
UNIT – III : TURING MACHINES (9+3 Periods)
Turing Machines – Language of a Turing Machine – Turing Machine as a Computing Device -
Techniques for TM – Modifications of Turing Machines – Two-way Infinite Tape, Equivalence of One
Way Infinite Tape and Two-way Infinite Tape Turing Machines – Multi Tape Turing Machines, Non-
deterministic Turing machine
Turing Machines – Language of a Turing Machine – Turing Machine as a Computing Device -
Techniques for TM – Modifications of Turing Machines – Two-way Infinite Tape, Equivalence of One
Way Infinite Tape and Two-way Infinite Tape Turing Machines – Multi Tape Turing Machines, Non-
deterministic Turing machine.
UNIT – IV : RECURSIVE AND RECURSIVELY ENUMERABLE
(9+3 Periods)
LANGUAGES
Recursively Enumerable and Recursive-Enumerating a Language –More General Grammars- Context –
Sensitive Languages and the Chomsky hierarchy- Not all Languages and Recursively Enumerable.
UNIT – V : UNDECIDABILITY (9+3 Periods)
A Language that is not Recursively Enumerable (RE) – An Undecidable Problem that is RE – Undecidable
Problems about Turing Machine – Rice Theorem for Recursive and Recursively Enumerable Languages –
Post‘s Correspondence Problem (PCP) – Modified Post Correspondence Problem
A Language that is not Recursively Enumerable (RE) – An Undecidable Problem that is RE –
Undecidable Problems about Turing Machine – Rice Theorem for Recursive and Recursively Enumerable
Languages – Post‘s Correspondence Problem (PCP) – Modified Post Correspondence Problem
Contact Periods:
Lecture: 45 Periods Tutorial: 15 Periods Practical: 0 Periods Total: 60 Periods
TEXT BOOKS:
1. John C. Martin “Introduction to languages and the theory of computation”, Third edition,
Mc Graw Hil, 2015.
REFERENCE BOOKS:
1. John E Hopcroft, Rajeev Motwani, Jeffrey D Ullman, “Introduction to Automata
Theory, Languages and Computation”, Third Edition, Pearson, 2013.
2. Michael Sipser, “Introduction to Theory of Computation”, Third Edition, Cengage
learning, 2013.
3. Adam Brooks Webber, “Formal languages: a practical introduction”, Jim Leisy, 2008.
COURSE OUTCOMES:
Upon completion of this course, the students will be able to,
CO1: Write Regular Expression/Context free grammar for the given language [Usage]
CO2: Construct Automata for the given language. [Usage]
CO3: Design Turing machines for the given problem [Usage]
CO4: Identify recursive and recursively enumerable language. ge]
CO5: Find whether the given problem is decidable or not. [Usage]
COURSE ARTICULATION MATRIX:
PO PO PO PO PO PO PO PO PO PO PO PO PSO PSO PSO PSO
CO 1 2 3 4 5 6 7 8 9 10 11 12 1 2 3 4
CO1 H H H H H L L H M L M H M L H
CO2 H H H H H L L H M L M H M L H
CO3 H H H H H L L H M L M H M L H
CO4 H H H H H L L H M L M H M L H
CO5 H H H H H L L H M L M H M L H
18SPC406 H H H H H L L H M L M H M L H
L-Low, M-Moderate(Medium), H-High
