WITH EFFECT FROM THE ACADEMIC YEAR 2016 - 2017
CS 303
AUTOMATA LANGUAGES AND COMPUTATION
|
Instruction |
4 |
Periods per week |
|
Duration of University Examination |
3 |
Hours |
|
University Examination |
75 |
Marks |
|
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, Non-deterministic Finite Automata, An application, Finite Automata with Epsilon Transitions.
Regular expressions & Languages: Regular Expressions, Finite Automata and Regular Expressions, Applications of Regular Expressions, Algebraic Laws for Regular Expressions.
UNIT-II
Properties of Regular Languages: Proving Languages not to be Regular, Closure properties of Regular Languages, Decision Properties of Regular Languages, Decision Properties of Regular Language, Equivalence and Minimization of Automata.
Context Free Grammars and Languages: Context free grammars, Parses Trees, Applications, Ambiguity in Grammars and Languages.
UNIT-III
Pushdown Automata: Definition, Languages of PDA, Equivalence of PDA’s and CFG’s Deterministic Pushdown Automata.
Properties of Context Free Languages: Normal Forms for Context Free Grammars, Pumping Lemma, closure properties, Decision Properties of CFL’s.
UNIT-IV
Introduction to Turing Machines: Problems that Computers cannot Solve, The Turing machines, Programming Techniques for Turing Machines, Extensions to the Turing 4 Machines Restricted Turing Machines, Turing machines and Computers.
UNIT-V
Un-decidability: 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. Intactable Problems: The Classes P and NP, an NP Complete Problem, A Restricted Satisfiability problem.
Suggested Reading :
- 1.John. E. Hopcroft, Rajeev Motwani, Jeffery, D. Ulman, Introduction
to Automata Theory, Languages and Computation, 3nd edition, Pearson Education-2007.
- 2.John C.Martin, Introduction to Languages and the Theory of Computation, 3rd edition Tata McGraw Hill, 2003.
- 3.Bernard M.Moret, The Theory of Computation, Pearson Education,