Hello There, Guest! RegisterLogin with Facebook
Login with Facebook

New Anna University Nov / Dec 2016 Examination Important Questions
New Anna University (UG / PG) Nov/Dec 2016 and Jan 2017 Theory , Practical Exam Timetable
>>> Anna University Sixth Semester Question Bank Collection (R2013) ECE,MECH,CSE,IT,EEE,CIVIL,EIE
>>> Anna University November/December 2015 Examination Question Papers
>>> Anna University Study Materials for all Departments
>>> Anna University Question Papers : April May June 2015 Question Papers | Nov Dec 2014 and Jan 2015 Question Papers

Register or Login to Submit Study Materials , Shoutbox and also to access Many Features !!

Vidyarthiplus Shop :: Handwritten Premium Lecture Notes
Share your Study Materials with us
Share your Study Materials with us : Click Here

CS6503 Theory Of Computation Hand Written Lecture Notes - Venkat Raman Edition
#1


   
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)

Arrow 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

 Arrow Attachment: click here



Reply

Subscribe


Recommend on Google