Introduction to Automata , Finite Automata , Nondeterministic Finite Automata , REGULAR EXPRESSIONS AND LANGUAGES , Properties of Regular Languages , Context-Free Grammars and Languages , Applications of Context-Free Grammars , Pushdown Automata , Languages of PDA , Deterministic Pushdown Automata , PROPERTIES OF CONTEXT-FREE LANGUAGES , Introduction to Turing Machines , UNDECIDABILITY ,
####
Hi friends, here Pankaj Yadav uploaded notes for Theory Of Computation with title **THEORY OF COMPUTATION LECTURE NOTES download for Bachelor of Technology in Computer Science and Engineering**. You can download this lecture notes,
ebook by clicking on the below file name or icon.

Module – I

Introduction to Automata: The Methods Introduction to Finite Automata, Structural

Representations, Automata and Complexity. Proving Equivalences about Sets, The

Contrapositive, Proof by Contradiction, Inductive Proofs: General Concepts of Automata

Theory: Alphabets Strings, Languages, Applications of Automata Theory.

Finite Automata: The Ground Rules, The Protocol, Deterministic Finite Automata: Definition

of a Deterministic Finite Automata, How a DFA Processes Strings, Simpler Notations for

DFA’s, Extending the Transition Function to Strings, The Language of a DFA

Nondeterministic Finite Automata: An Informal View. The Extended Transition Function, The Languages of an NFA, Equivalence of Deterministic and Nondeterministic Finite Automata.

Finite Automata With Epsilon-Transitions: Uses of Î-Transitions, The Formal Notation for an

Î-NFA, Epsilon-Closures, Extended Transitions and Languages for Î-NFA’s, Eliminating Î-

Transitions.

Module – II

Regular Expressions and Languages: Regular Expressions: The Operators of regular

Expressions, Building Regular Expressions, Precedence of Regular-Expression Operators,

Precedence of Regular-Expression Operators

Finite Automata and Regular Expressions: From DFA’s to Regular Expressions, Converting

DFA’s to Regular Expressions, Converting DFA’s to Regular Expressions by Eliminating States,

Converting Regular Expressions to Automata.

Algebraic Laws for Regular Expressions:

Properties of Regular Languages: The Pumping Lemma for Regular Languages, Applications

of the Pumping Lemma Closure Properties of Regular Languages, Decision Properties of

Regular Languages, Equivalence and Minimization of Automata,

Context-Free Grammars and Languages: Definition of Context-Free Grammars, Derivations

Using a Grammars Leftmost and Rightmost Derivations, The Languages of a Grammar,

Parse Trees: Constructing Parse Trees, The Yield of a Parse Tree, Inference Derivations, and

Parse Trees, From Inferences to Trees, From Trees to Derivations, From Derivation to Recursive

Inferences,

Applications of Context-Free Grammars: Parsers, Ambiguity in Grammars and Languages:

Ambiguous Grammars, Removing Ambiguity From Grammars, Leftmost Derivations as a Way

to Express Ambiguity, Inherent Anbiguity

Module – III

Pushdown Automata: Definition Formal Definition of Pushdown Automata, A Graphical

Notation for PDA’s, Instantaneous Descriptions of a PDA,

Languages of PDA: Acceptance by Final State, Acceptance by Empty Stack, From Empty Stack

to Final State, From Final State to Empty Stack

Equivalence of PDA’s and CFG’s: From Grammars to Pushdown Automata, From PDA’s to

Grammars

Deterministic Pushdown Automata: Definition of a Deterministic PDA, Regular Languages

and Deterministic PDA’s, DPDA’s and Context-Free Languages, DPDA’s and Ambiguous

Grammars

Properties of Context-Free Languages: Normal Forms for Context-Free Grammars, The

Pumping Lemma for Context-Free Languages, Closure Properties of Context-Free Languages,

Decision Properties of CFL’s

Module –IV

Introduction to Turing Machines: The Turing Machine: The Instantaneous Descriptions for

Turing Machines, Transition Diagrams for Turing Machines, The Language of a Turing

Machine, Turing Machines and Halting

Programming Techniques for Turing Machines, Extensions to the Basic Turing Machine,

Restricted Turing Machines, Turing Machines and Computers,

Undecidability: A Language That is Not Recursively Enumerable, Enumerating the Binary

Strings, Codes for Turing Machines, The Diagonalization Language

An Undecidable Problem That Is RE: Recursive Languages, Complements of Recursive and RE

languages, The Universal Languages, Undecidability of the Universal Language

Undecidable Problems About Turing Machines: Reductions, Turing Machines That Accept the

Empty Language. Post’s Correspondence Problem: Definition of Post’s Correspondence

Problem, The “Modified” PCP, Other Undecidable Problems: Undecidability of Ambiguity for

CFG’s

Login for leave comment

## No any Comment yet!