Theory Of Computation Premium Lecture Notes, Prepared by Venkat raman. Specially for Computer Science Engineering . Syllabus Covered based on Anna University B.E Computer Science Engineering,Can Also used for Syllabus of (Regulation 2008).

CONTENT:

UNIT-1 AUTOMATA (Pg.no:73)

UNIT-2 REGULAR EXPRESSION AND LANGUAGE (Pg.no:52)

UNIT-3 CONTEXT-FREE GRAMMER AND LANGUAGE (Pg.no:60)

UNIT-4 PROPERTIES OF CONTEXT-FREE LANGUAGE (Pg.no:63)

UNIT-5 UNDECIDABALITY (pg.no:7)

Attachment: click here

UNIT-1

AUTOMATA

Theorem

Properties of transition function

For all string w and input symbol a

Basis

Formal proof

Type

1. Deductive proof

2. Inductive proof

Various form of proof

1. Deductive proof

2. Reduction to definition

3. Additional form of proof

4. Other theorem form

5. Not if and only form

Additional form of proof

1. Proof about set

2. Proof by contradiction

3. Contrapositive

4. Proof by counter

UNIT-2

REGULAR EXPRESSION AND LANGUAGE

Introduction

Steps

Finite automoto

Set of transition rule

Myhill-nerode theorem

New state of DFA

Algorithm for making pair of inequvalent state

Regular expression

Klnee theorem or aeden theorem

Construction

Different sum

Pumping lemma

Closure under intersection theorem

Closure under difference

Homomorphism

Inverse homomorphism

UNIT-3

CONTEXT-FREE GRAMMER AND LANGUAGE

PDA construction

Ambiguous

Derivation tree

Deterministic PDA

Non deterministic PDA

Acceptance by final state

Acceptance by empty stack

CFG to PDA

Parse tree

Transistion function

Each production

Context free language

UNIT-4

PROPERTIES OF CONTEXT-FREE LANGUAGE

Turning machine

Programming techniques for TM

1. Storage finite control

2. Multiple tracks

3. Subroutine

4. Checking off symbol

Multiple track in turning machine

Example of design turning machine with multiple track

Closure under concentration

Intersection

Complementation

Property of CFL

UNIT-5

UNDECIDABALITY

Halting problem

NP hard problem

NP complete problem

Attachment: click here