Theory of Computation: II B. Tech. - II Semester L T P C Course Code: A3CS10 4 1 - 4

Download as pdf or txt
Download as pdf or txt
You are on page 1of 2

Department of Computer Science and Engineering

THEORY OF COMPUTATION
II B. Tech. - II Semester L T P C
Course Code: A3CS10 4 1 - 4

COURSE OVERVIEW:
Formal languages and automata theory deals with the concepts of automata, formal languages,
grammar, computability and decidability. The reasons to study Formal Languages and Automata
Theory are Automata Theory provides a simple, elegant view of the complex machine that we call a
computer. Automata Theory possesses a high degree of permanence and stability, in contrast with
the ever-changing paradigms of the technology, development, and management of computer
systems. Further, parts of the Automata theory have direct bearing on practice, such as Automata on
circuit design, compiler design, and search algorithms; Formal Languages and Grammars on
compiler design; and Complexity on cryptography and optimization problems in manufacturing,
business, and management. Last, but not least, research oriented students will make good use of the
Automata theory studied in this course.

COURSE OBJECTIVES:
1. To give an overview of the theoretical foundations of computer science from the perspective
of formal languages
2. To illustrate finite state machines to solve problems in computing
3. To explain the hierarchy of problems arising in the computer sciences.
4. To familiarize Regular grammars, context frees grammar.

Course Outcomes: At the end of the course students will be able to:
1. To use basic concepts of formal languages of finite automata techniques
2. To Design Finite Automata’s for different Regular Expressions and Languages
3. To Construct context free grammar for various languages
4. To solve various problems of applying normal form techniques, push down automata and
Turing Machines
5. To participate in GATE, PGECET and other competitive examinations

SYLLABUS
UNIT - I
FINITE AUTOMATA (FA): Introduction, Deterministic Finite Automata (DFA) -Formal definition,
simpler notations (state transition diagram, transition table), language of a DFA. Nondeterministic
Finite Automata (NFA)- Definition of NFA, language of an NFA, Equivalence of Deterministic and
Nondeterministic Finite Automata, Applications of Finite Automata, Finite Automata with Epsilon
Transitions, Eliminating Epsilon transitions, Minimization of Deterministic Finite Automata, Finite
automata with output (Moore and Mealy machines) and Inter conversion.

UNIT - II
REGULAR EXPRESSIONS (RE): Introduction, Identities of Regular Expressions, Finite Automata
and Regular Expressions- Converting from DFA’s to Regular Expressions, Converting Regular
Expressions to Automata, applications of Regular Expressions.
REGULAR GRAMMARS: Definition, regular grammars and FA, FA for regular grammar, Regular
grammar for FA. Proving languages to be non-regular -Pumping lemma, applications, Closure
properties of regular languages.

UNIT - III
CONTEXT FREE GRAMMER (CFG): Derivation Trees, Sentential Forms, Rightmost and Leftmost
derivations of Strings. Ambiguity in CFG’s, Minimization of CFG’s, CNF, GNF, Pumping Lemma for
CFL’s, Enumeration of Properties of CFL ( Proof’s omitted ).

UNIT – IV
PUSHDOWN AUTOMATA: Definition, Model, Acceptance of CFL, Acceptance by Final State and
Acceptance by Empty stack and its Equivalence, Equivalence of CFG and PDA.
TURING MACHINES (TM): Formal definition and behaviour, Languages of a TM, TM as accepters,

MLR Institute of Technology- UG - Autonomous-Regulations & Syllabus – MLR - 17 Page | 67


Department of Computer Science and Engineering

and TM as a computer of integer functions, Types of TMs.

UNIT V
RECURSIVE AND RECURSIVELY ENUMERABLE LANGUAGES (REL): Properties of recursive
and recursively enumerable languages, Universal Turing machine, The Halting problem, Undecidable
problems about TMs. Context sensitive language and linear bounded automata (LBA), Chomsky
hierarchy, Decidability, Post's correspondence problem (PCP), undecidability of PCP.

TEXT BOOKS:
1. John E. Hopcroft, Rajeev Motwani, Jeffrey D. Ullman (2007), Introduction to Automata Theory
Languages andComputation, 3rdedition, Pearson Education, India.

REFERENCE BOOKS:
1. K. L. P Mishra, N. Chandrashekaran (2003), Theory of Computer Science-Automata
Languages and Computation, 2nd edition, Prentice Hall of India, India.

MLR Institute of Technology- UG - Autonomous-Regulations & Syllabus – MLR - 17 Page | 68

You might also like