syllabus
UNIT - I
Introduction to Finite Automata, Structural Representations, Automata and Complexity, the
Central Concepts of Automata Theory – Alphabets, Strings, Languages, Problems.
Deterministic Finite Automata, Nondeterministic Finite Automata, an application: Text
Search, Finite Automata with Epsilon-Transitions.
UNIT - II
Regular Expressions, Finite Automata and Regular Expressions, Applications of Regular
Expressions, Algebraic Laws for Regular Expressions, Properties of Regular LanguagesPumping Lemma for Regular Languages, Applications of the Pumping Lemma, Closure
Properties of Regular Languages, Decision Properties of Regular Languages, Equivalence
and Minimization of Automata.
UNIT - III
Context-Free Grammars: Definition of Context-Free Grammars, Derivations Using a
Grammar, Leftmost and Rightmost Derivations, the Language of a Grammar, Sentential
Forms, Parse Tress, Applications of Context-Free Grammars, Ambiguity in Grammars and
Languages.
Push Down Automata,: Definition of the Pushdown Automaton, the Languages of a PDA,
All JNTU World
Equivalence of PDA's and CFG's, Deterministic Pushdown Automata.
UNIT - IV
Normal Forms for Context- Free Grammars, the Pumping Lemma for Context-Free
Languages, Closure Properties of Context-Free Languages. Decision Properties of CFL's -
Complexity of Converting among CFG's and PDA's, Running time of conversions to
Chomsky Normal Form.
Introduction to Turing Machines-Problems That Computers Cannot Solve, The Turing
Machine, Programming Techniques for Turing Machines, Extensions to the basic Turing
machine, Restricted Turing Machines, Turing Machines, and Computers
UNIT - V
Undecidability: A Language that is Not Recursively Enumerable, An Undecidable Problem
That is RE, Undecidable Problems about Turing Machines, Post's Correspondence Problem,
Other Undecidable Problems, Intractable Problems: The Classes P and NP, An NP-Complete
Problem.
