T
L P C
CS3452 THEORY OF COMPUTATION
3 0 0 3
COURSE OBJECTIVES:
● o understand foundations of computation including automata theory
T
● To construct models of regular expressions and languages.
● To design context free grammar and push down automata
● To understand Turing machines and their capability
● To understand Undecidability and NP class problems
UNIT1:AUTOMATAANDREGULAREXPRESSIONS 9
eedforautomatatheory- Introductiontoformalproof–FiniteAutomata(FA)–DeterministicFinite
N
Automata(DFA)–Non-deterministicFiniteAutomata(NFA)–EquivalencebetweenNFAandDFA–
Finite Automata with Epsilon transitions –EquivalenceofNFAandDFA-EquivalenceofNFAswith
and without ε-moves- Conversion of NFA into DFA – Minimization of DFAs
UNIT 2: REGULAR EXPRESSIONS AND LANGUAGES 9
Regular expression – RegularLanguages-EquivalenceofFiniteAutomataandregularexpressions–
Proving languages to be not regular (Pumping Lemma) – Closure properties of regular languages.
UNIT 3: CONTEXT FREE GRAMMAR AND PUSH DOWN AUTOMATA 9
Bubblesort–selectionsort–insertionsort–mergesort–quicksort–analysisofsortingalgorithms–
linearsearch–binarysearch–hashing–hashfunctions–collisionhandling–loadfactors,rehashing,
and efficiency
UNIT 4:NORMAL FORMS AND TURING MACHINES 9
Normal forms for CFG – Simplification of CFG- Chomsky Normal Form (CNF) and Greibach
NormalForm(GNF)–PumpinglemmaforCFL–ClosurepropertiesofContextFreeLanguages–
TuringMachine:Basicmodel–definitionandrepresentation–InstantaneousDescription–Language
acceptance by TM – TM as Computer of Integer functions – Programming techniques for Turing
machines (subroutines).
UNIT 5: UNDECIDABILITY 9
Unsolvable Problems and Computable Functions –PCP-MPCP- Recursive and recursively
enumerablelanguages–Properties- UniversalTuringmachine- TractableandIntractableproblems-
P and NP completeness – Kruskal’s algorithm – Travelling Salesman Problem- 3-CNF SAT
problems.
Total Hours - 45
OURSE OUTCOMES:
C
CO1:Construct automata theory using Finite Automata
CO2: Write regular expressions for any pattern
CO3:Design context free grammar and Pushdown Automata
CO4: Design Turing machine for computational functions
CO5:Differentiate between decidable and undecidable problems
TEXT BOOKS:
1. Hopcroft J.E., Motwani R. & Ullman J.D., "Introduction to Automata Theory, Languages and
Computations", 3rd Edition, Pearson Education, 2008.
2. John C Martin , "Introduction to Languages and the Theory of Computation", 4th Edition, Tata
McGraw Hill, 2011.
REFERENCE BOOKS:
1 . Harry R Lewis and Christos H Papadimitriou , "Elements of the TheoryofComputation",2nd
Edition, Prentice Hall of India, 2015.
2. Peter Linz, "AnIntroductiontoFormalLanguageandAutomata",6thEdition,Jones&Bartlett,
2016.
3. K.L.P.Mishra andN.Chandrasekaran,“TheoryofComputerScience:AutomataLanguagesand
Computation”, 3rd Edition, Prentice Hall of India, 2006.
CO’s-PO’s & PSO’s MAPPING
PO’ PSO’s
CO’s s
1 2 3 4 5 6 7
8
9 10 1
1 12
1
2
3
1 1 3 2 3 - - - - 1 1 2 3 1 3 2
2 2 2 3 2 1 - - - 3 3 2 3 3 1 2
3 2 2 3 2 1 - - - 1 3 1 2 1 2 2
4 2 2 2 1 - - - - 1 3 3 2 1 3 2
5 2 2 2 1 1 - - - 1 1 3 2 3 1 3
VG
A 2 2 2 2 1 - - - 1 2 2 2 2 2 2
