# Theory of Computation

Course Code:ULZHS0084

Author:uLektz

University:

Regulation:2013

Categories:Arts and Science

Format : ePUB3 (DRM Protected)

Type :eBook

FREE

Description :Theory of Computation of ULZHS0084 covers the latest syllabus prescribed by General for All University 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.