The site would be on maintenance from 8th Jul 2019 2.00pm to 8:00pm. You may experience some issue during this time.

Book Details

Theory of Computation

Theory of Computation

Published by uLektz

Course Code : ULZ0194
Author : uLektz
University : General for All University
Regulation : 2017
Categories : Computer Science
Format : ico_bookePUB3 (DRM Protected)
Type : eBook

FREE

Buy Now

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