Full Notes of CS3452 THEORY OF COMPUTATION
Anna University Question April / May 2023
Anna University Question Nov / Dec 2023
CS3452 THEORY OF
COMPUTATION L T P C 3 0 0 3
COURSE OBJECTIVES:
To understand the foundations
of computation including automata theory
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
UNIT I AUTOMATA AND
REGULAR EXPRESSIONS 9
Need for automata theory
- Introduction to formal proof – Finite Automata (FA) – Deterministic Finite Automata
(DFA) – Non-deterministic Finite Automata (NFA) – Equivalence between NFA and
DFA –Finite Automata with Epsilon transitions – Equivalence of NFA and DFA-
Equivalence of NFAs with and without ε-moves- Conversion of NFA into DFA –
Minimization of DFAs.
UNIT II REGULAR
EXPRESSIONS AND LANGUAGES 9
Regular expression –
Regular Languages- Equivalence of Finite Automata and regular expressions –
Proving languages to be not regular (Pumping Lemma) – Closure properties of
regular languages.
UNIT III CONTEXT FREE
GRAMMAR AND PUSH DOWN AUTOMATA 9
Types of Grammar -
Chomsky‘s hierarchy of languages -Context-Free Grammar (CFG) and Languages –
Derivations and Parse trees – Ambiguity in grammars and languages – Push Down Automata
(PDA): Definition – Moves - Instantaneous descriptions -Languages of pushdown automata
– Equivalence of pushdown automata and CFG-CFG to PDA-PDA to CFG –
Deterministic Pushdown Automata.
UNIT IV NORMAL FORMS AND
TURING MACHINES 9
Normal forms for CFG –
Simplification of CFG- Chomsky Normal Form (CNF) and Greibach Normal Form (GNF)
– Pumping lemma for CFL – Closure properties of Context Free Languages –Turing Machine
: Basic model – definition and representation – Instantaneous Description –
Language acceptance by TM – TM as Computer of Integer functions – Programming
techniques for Turing machines (subroutines).
UNIT V UNDECIDABILITY 9
Unsolvable Problems and
Computable Functions –PCP-MPCP- Recursive and recursively enumerable languages
– Properties - Universal Turing machine -Tractable and Intractable problems - P
and NP completeness – Kruskal’s algorithm – Travelling Salesman Problem- 3-CNF
SAT problems.
COURSE OUTCOMES:
At the end of this
course, the students will be able to:
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
TOTAL:45 PERIODS
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.
REFERENCES
1. Harry R Lewis and
Christos H Papadimitriou , "Elements of the Theory of Computation", 2nd
Edition, Prentice Hall of India, 2015.
2. Peter Linz, "An
Introduction to Formal Language and Automata", 6th Edition, Jones &
Bartlett, 2016.
3. K.L.P.Mishra and
N.Chandrasekaran, “Theory of Computer Science: Automata Languages and Computation”,
3rd Edition, Prentice Hall of India, 2006.
Click here to download
CS3391 OBJECT ORIENTED PROGRAMMING L T P C 3 0 0 3
COURSE OBJECTIVES:
· To understand
Object Oriented Programming concepts and basics of Java programming language
· To know the
principles of packages, inheritance and interfaces
· To develop a java
application with threads and generics classes
· To define
exceptions and use I/O streams
· To design and
build Graphical User Interface Application using JAVAFX
UNIT I INTRODUCTION TO
OOP AND JAVA 9
Overview of OOP – Object
oriented programming paradigms – Features of Object Oriented Programming – Java
Buzzwords – Overview of Java – Data Types, Variables and Arrays – Operators –
Control Statements – Programming Structures in Java – Defining classes in Java
– Constructors-Methods -Access specifiers - Static members- JavaDoc comments
Click here to download
CD3291 DATA STRUCTURES AND ALGORITHMS L T P C 3 0 0 3
COURSE OBJECTIVES:
·
To understand the concepts of ADTs
·
To design linear data structures – lists, stacks, and queues
·
To understand sorting, searching, and hashing algorithms
·
To apply Tree and Graph structures
UNIT I ABSTRACT DATA TYPES 9
Abstract Data Types (ADTs) – ADTs and classes –
introduction to OOP – classes in Python – inheritance – namespaces – shallow
and deep copying Introduction to analysis of algorithms – asymptotic notations
– divide & conquer – recursion – analyzing recursive algorithms
Click here to download
CS3352 DIGITAL PRINCIPLESAND COMPUTER ORGANIZATION L T P C 3 0 2 4
COURSE OBJECTIVES:
· To analyze and
design combinational circuits.
· To analyze and
design sequential circuits
· To understand the
basic structure and operation of a digital computer.
· To study the
design of data path unit, control unit for processor and to familiarize with
the hazards.
· To understand the
concept of various memories and I/O interfacing.
UNIT I COMBINATIONAL
LOGIC 9
Combinational Circuits –
Karnaugh Map - Analysis and Design Procedures – Binary Adder – Subtractor –
Decimal Adder - Magnitude Comparator – Decoder – Encoder – Multiplexers -
Demultiplexers
Click here to download
CS3353 FOUNDATIONS OFDATA SCIENCE L T P C 3 0 0 3
COURSE OBJECTIVES:
· To understand the
data science fundamentals and process.
· To learn to
describe the data for the data science process.
· To learn to
describe the relationship between data.
· To utilize the
Python libraries for Data Wrangling.
· To present and
interpret data using visualization libraries in Python
UNIT I INTRODUCTION 9
Data Science: Benefits
and uses – facets of data - Data Science Process: Overview – Defining research
goals – Retrieving data – Data preparation - Exploratory Data analysis – build
the model– presenting findings and building applications - Data Mining - Data
Warehousing – Basic Statistical descriptions of Data
UNIT II DESCRIBING DATA 9
Types of Data - Types of
Variables -Describing Data with Tables and Graphs –Describing Data with
Averages - Describing Variability - Normal Distributions and Standard (z)
Scores
Click here to download
MA3354DISCRETE MATHEMATICS L T P C 3 1 0 4
COURSE
OBJECTIVES:
· To extend student’s logical and
mathematical maturity and ability to deal with abstraction.
· To introduce most of the basic
terminologies used in computer science courses and application of ideas to
solve practical problems.
· To understand the basic concepts of
combinatorics and graph theory.
· To familiarize the applications of
algebraic structures.
· To understand the concepts and
significance of lattices and boolean algebra which are widely used in computer
science and engineering.
UNIT I
LOGIC AND PROOFS 9+3
Propositional
logic – Propositional equivalences - Predicates and quantifiers – Nested
quantifiers – Rules of inference - Introduction to proofs – Proof methods and
strategy.
UNIT
II COMBINATORICS 9+3
No comments:
Post a Comment