JAWAHARLAL NEHRU TECHNOLOGICAL UNIVERSITY HYDERABAD

Course Objectives:

• To provide introduction to some of the central ideas of theoretical computer science from the perspective of formal languages.
• To introduce the fundamental concepts of formal languages, grammars and automata theory.
• Classify machines by their power to recognize languages.
• Employ finite state machines to solve problems in computing.
• To understand deterministic and non-deterministic machines.
• To understand the differences between decidability and undecidability.

Course Outcomes:

• Able to understand the concept of abstract machines and their power to recognize the languages.
• Able to employ finite state machines for modeling and solving computing problems.
• Able to design context free grammars for formal languages.
• Able to distinguish between decidability and undecidability.
• Able to gain proficiency with mathematical tools and formal methods.

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 Languages- Pumping 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, 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.

TEXT BOOKS:

• 1. Introduction to Automata Theory, Languages, and Computation, 3 nd Edition, John E. Hopcroft, Rajeev Motwani, Jeffrey D. Ullman, Pearson Education.
• 2. Introduction to the Theory of Computation, Michael Sipser, 3rd edition, Cengage Learning.

REFERENCE BOOKS:

• 1. Introduction to Languages and The Theory of Computation, John C Martin, TMH.
• 2. Introduction to Computer Theory, Daniel I.A. Cohen, John Wiley.
• 3. A Text book on Automata Theory, P. K. Srimani, Nasir S. F. B, Cambridge University Press.
• 4. Introduction to Formal languages Automata Theory and Computation Kamala Krithivasan, Rama R, Pearson.
• 5. Theory of Computer Science – Automata languages and computation, Mishra and Chandrashekaran, 2nd edition, PHI.