BIT 306                                                         WITH EFFECT FROM THE ACADEMIC YEAR 2012-2013

THEORY OF AUTOMATA

Instruction                                                                                                           4 Periods per week
Duration of University Examination                                                                   3Hours
University Examination                                                                                     75Marks
Sessional                                                                                                            25 Marks

UNIT-I
Automata:Introduction to Finite Automata, Central Concepts of
Automata Theory, Finite Automata An informal Picture of Finite
Automata, Deterministic Finite Automata, Nondeterministic Finite
Automata, An Application, Finite Automata with Epsilon Transitions.
Regular Expression and Languages:Regular Expressions, Finite
AutomataandRegular Expression, Applications of Regular Expressions,
Algebraic Laws for Regular Expression.

UNIT-Il
Properties of RegularLanguages :Proving Languages not to be Regular, Closure Properties of Regular Languages, Decision Properties of Regular Languages,Equivalanceand Minimization of Automata.ContextFreeGrammars andLanguages :Context-FreeGrammar s, Parse Trees, Applications, Ambiguityin Grammars and Languages.

UNIT-III
PushdownAutomata :Definition, Language of PDA, Equivalence of
PDA’s and;CFG’s.Deterministic Pushdown Automata.Propcrtiesof
Context FreeLanguages :Normal Forms for Context-Free Grammars,
Pumping Lemma, closure properties, Decision Properties ofCFL’s.

UNIT-IV
Introduction toTurning Machines:Problems that Computer Cannot
Solve, The Turning, Machine, Programming Techniques for Turning
Machines, Extensions to the Turning4Machines, Restricted Turning
Machines, Turning Machine and Computers. 

UNIT-V
Undecidability:A language that is not Recursively Enumerable. An
undecidableProblemthatisRE,Undecidableproblems aboutTurning
Machines, Post’s Correspondence Problem, OtherUndecidable
Problems.
Intractable Problems:The Classes P and NPAnNP Complete Problem,
A RestrictedsatisfiabilityProblem.

SujgestedReading:
1.John E.HopcroftRajeevMotwani,JeffeiyDUlman,liuroductionto Automata Theory Languages and Computation,Second edition, Pearson Education, 2007.

References:
1. John C.Martin,Introduction toLanguages and the Theory ofComputation,3rd edition,TataMcGrawHill,2003.
2.Cohen DanielI.E.“Introduction to Computer Theory”2nd edition, Wiley India, 2007.
3.BernardMoret,TheTheory of Computation,PearsonEducation,
2002.