Theory of Computation

23CS1502- THEORY OF COMPUTATION     

OBJECTIVES

• To know about Chomsky hierarchy for organizing languages.

•  To introduce concepts in automata theory and theory of computation.

•  To identify different formal language classes and their relationships.

•  To design grammars and recognizers for different formal languages.

•  To understand undecidability and decide on languages that is undecidable.

UNIT I   FINITE AUTOMATA    9                             

Introduction to formal proof — Additional forms of Proof — Inductive Proofs -Finite Automata (FA) – Deterministic Finite Automata (DFA) – Non-deterministic Finite Automata (NFA) – Finite Automata with Epsilon Transitions – NFA to DFA conversion – Epsilon NFA to DFA conversion-. Applications and Limitation of FA.

UNIT II  RREGULAR EXPRESSION AND REGULAR LANGUAGES   9         

Definition - Operators of regular expression - Algebraic laws for Regular expressions– Equivalence of FA and Regular Expressions – Minimization of Finite Automata - Pumping Lemma for Regular Languages. Closure properties of Regular Languages /Sets.

UNIT III CONTEXT FREE GRAMMAR & PUSH DOWN AUTOMATA    9  

Context-Free Grammar (CFG) – Derivation Trees – Ambiguity in Grammars and Languages – Definition of the Pushdown Automata – Language of a Pushdown Automata – Equivalence of Pushdown Automata and CFG – Pumping Lemma for CFL –  Closure Properties of CFL- Deterministic Pushdown Automata.

UNIT IV  PROPERTIES OF CONTEXT-FREE LANGUAGES   9

Simplification of Context-free Grammar – Chomsky Normal Form – Greibach Normal Form - TURING MACHINES (TM) - Formal definition and behavior, Languages of a TM - Turing Machine as a Computing Device and Language Acceptor - Techniques for TM .

UNIT V UNDECIDABILITY 9

Recursive and Recursively Enumerable Languages - Halting problem - Introduction to Undecidability and Reducibility - Undecidable problems about TMs - Post correspondence problem (PCP) - Modified PCP .

TOTAL : 45 PERIODS

COURSE OUTCOMES

Upon successful completion of the course, students should be able to:

•  Construct finite automata, regular expression for any pattern.

•  Write context free grammar for any construct.

•  Build pushdown automata to recognize a context free language.

•  Design Turing machines for any language.

•  Propose computation solutions using Turing Machine

•  Drive whether a problem is decidable or not.

TEXT BOOKS

1. John E. Hopcroft ,Rajeev Motwani, Jeffery D. Ullman, Introduction to Automata Theory, Languages and Computations, Third Edition, Pearson Education ,2009.

2. Kamala Krithivasan and R. Rama, Introduction to Formal Languages, Automata Theory and Computation, Pearson Education, Delhi, 2009.

REFERENCE BOOKS

1. Harry R. Lewis and Christos H. Papadimitriou, Elements of the theory of Computation, Second Edition, Prentice-Hall of India Pvt. Ltd, 2003.

2. J. Martin, Introduction to Languages and the Theory of Computation, Third Edition, Tata Mc Graw Hill, New Delhi, 2003.

3. Micheal Sipser, “Introduction of the Theory and Computation”, Thomson Learning, 1997.