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 hereUNIT-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
