Book Details

Theory of Computation

Theory of Computation

Published by uLektz

Course Code:CS6503

Author:uLektz

University: Anna University, Tamil Nadu

Regulation:2013

Categories:Computer Science

Format : ico_bookePUB3 (DRM Protected)

Type :eBook

FREE

Buy Now

Description :Theory of Computation of CS6503 covers the latest syllabus prescribed by Anna University, Tamil Nadu for regulation 2013. Author: uLektz, Published by uLektz Learning Solutions Private Limited.

Note : No printed book. Only ebook. Access eBook using uLektz apps for Android, iOS and Windows Desktop PC.

Topics
UNIT I FINITE AUTOMATA

1.1 Introduction

1.2 Basic Mathematical Notation and techniques

1.3 Finite State systems - Basic Definitions

1.4 Finite Automaton - DFA - NDFA - Finite Automaton with €- moves

1.5 Regular Languages

1.6 Regular Expression

1.7 Equivalence of NFA and DFA

1.8 Equivalence of NDFA’s with and without €-moves

1.9 Equivalence of finite Automaton and regular expressions

1.10 Minimization of DFA

1.11 Pumping Lemma for Regular sets - Problems based on Pumping Lemma.

UNIT II GRAMMARS

2.1 Grammar Introduction

2.2 Types of Grammar

2.3 Context Free Grammars and Languages

2.4 Derivations and Languages

2.5 Ambiguity

2.6 Relationship between derivation and derivation trees

2.7 Simplification of CFG

2.8 Elimination of Useless symbols

2.9 Unit productions

2.10 Null productions

2.11 Greibach Normal form

2.12 Chomsky normal form

2.13 Problems related to CNF and GNF

UNIT III PUSHDOWN AUTOMATA

3.1 Pushdown Automata - Definitions

3.2 Moves

3.3 Instantaneous descriptions

3.4 Deterministic pushdown automata

3.5 Equivalence of Pushdown automata and CFL

3.6 Pumping lemma for CFL - Problems based on pumping Lemma

UNIT IV TURING MACHINES

4.1 Definitions of Turing machines

4.2 Models - Computable languages and functions

4.3 Techniques for Turing machine construction

4.4 Multi head and Multi tape Turing Machines

4.5 The Halting problem

4.6 Partial Solvability

4.7 Problems about Turing machine - Chomskian hierarchy of languages

UNIT V UNSOLVABLE PROBLEMS AND COMPUTABLE FUNCTIONS

5.1 Unsolvable Problems and Computable Functions

5.2 Primitive recursive functions

5.3 Recursive and recursively enumerable languages

5.4 Universal Turing machine.

5.5 MEASURING AND CLASSIFYING COMPLEXITY: Tractable Problems- Intractable problems - Tractable and possibly intractable problems

5.6 P and NP completeness

5.7 Polynomial time reductions.

loading