JAWAHARLAL NEHRU TECHNOLOGICAL UNIVERSITY HYDERABAD

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

Regular Languages –Finite Automata, Formal definition of finite automaton, Examples of finite automata, Formal definition of computation, Designing finite automata, The regular operations, Non determinism, formal definition of nondeterministic finite automaton, equivalence of NFAs and DFAs, closure under the regular operations, Regular Expressions, formal definition of a regular expression, equivalence with finite automata, Nonregular languages, The pumping lemma for regular languages.

UNIT - II

Context-Free languages, Context-free grammars, formal definition of a Context-free grammar, Examples of context-free grammars, Designing context-free grammars, Ambiguity, Chomsky normal form, Pushdown Automata, Examples of pushdown Automata, Equivalence with context-free grammars, Non-context-free languages, The pumping lemma for context-free languages.

UNIT - III

The Church-Turing Thesis - Turing machines, Formal definition of turing machine, Examples of turing machines, Variants of turing machines, Multitape turing machines, Nondeterministic turing machine, Enumerators, Equivalence with other models, The definition of algorithm, Hilbert’s problem, Terminology of describing turing machines.

UNIT - IV

Decidability – Decidable languages, Decidable problems concerning regular languages, Decidable problems concerning context-free languages, The halting problem, The diagonalization method, The halting method is undecidable, A turing –unrecognizable language, Reducibility – Undecidable problems for language theory, Reductions via computations histories, A simple undecidable problem, Mapping reducibility, computable functions, Formal definition of mapping reducibility.

UNIT - V

Time Complexity – Measuring complexity, Big – O and small-o notation, Analyzing algorithms, Complexity relationships among models, The class P, Polynomial time, examples of problems in P, The class NP, Examples of problems in NP, The P versus NP question, NP-Completeness, polynomial time reducibility, Definition of NP-Completeness, The Cook-Levin Theorem, Additional NP- Complete problems, The vertex cover problem, The Hamiltonian path problem, The subset sum problem.

TEXTBOOKS:

• 1. Introduction to the theory of computation, Micheal Sipser, Third Edition, Cengage Learning.

REFERENCES:

• 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. M. Tech - CSE/CS – I Year – II Sem