Theory of Computation

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

FREE

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.