March 12, 2010

CS5001 – THEORY OF COMPUTATION


Anna University Tiruchirappalli - 620 024
Regulations 2007
Sylllabus
M.E. COMPUTER SCIENCE AND ENGINEERING ELECTIVES

CS5001 – THEORY OF COMPUTATION


UNIT I FINITE AUTOMATA AND REGULAR LANGUAGES 9

Finite Automata and Regular Languages – Regular Expressions and Regular Languages – Non
Determinism and Kleenes Theorem – Equivalence of DFA and NFA – Finite Automation with E–
moves – Equivalence of Regular Expression and NFA with E–moves – Pumping Lemma for Regular Sets.

UNIT II CONTEXT FREE LANGUAGES 9
Context Free Languages – Derivation and Languages – Relationship between Derivation and Derivation Trees – Simplification of Context Free Grammars – Normal Forms for Context Free
Grammars – CNF – GNF.

UNIT III PUSH DOWN AUTOMATA (PDA) 9
Acceptance by PDA – Pushdown Automata and Context Free Languages – Pumping Lemma for
CFL – Deterministic Context Free Languages and Deterministic Pushdown Automata.

UNIT IV TURING MACHINE 9
Context Sensitive Languages and LBA – Turing Machine (Definition And Examples) – Computable Languages and Functions – Church Turing Hypothesis – Universal Turing Machine – P and NP Problems – NP – Complete.

UNIT V UNSOLVABLE PROBLEMS 9
Unsolvable Problems – Rice Theorem – Post's Correspondence Problem – Recursive and Recursively Enumerable Languages.

Total: 45
TEXT BOOKS
1. Hopcroft and Ullman, “Introduction to Automata, Languages and Computation”, 2nd
Edition, Narosa Publishers, 2000.
2. John C. Martin, “Introduction to languages and the Theory of Computation”, 2nd Edition,
McGraw Hill, 1997.

REFERENCES
1. A. M. Natarajan, A. Tamilarasi & P. Balasubramani, “Theory of Computation”, New Age
International publishers, 2002.
2. K.L.P.Mishra, N.Chandrasekaran, “Theory of Computation”, 2nd Edition, EEE, Prentice Hall
of India, 1998.
3. Peter Linz, “An Introduction to formal languages and Automata”, Narosa Publishing House,
2001.
4. Harry R. Lewis, Christos H. Papadimitriou, “Elements of Theory of Computation”, Prentice
Hall, 2002.

FEEL USEFUL PLEASE GIVE +1

0 comments :

Post a Comment

Get Syllabus in your Mail

Labels

Accenture Admission Notice - 2010 Admission Notification Anna University Anna University Chennai Anna University Question Papers Anna University Trichy Apparel Technology and Management Aptitude Questions Arts and Science Colleges Biomedical Engineering C and CPP Ebooks Calicut University CBSE Question papers Civil Engineering Civil Service Exams Colleges in India Colleges Result Computer Science Engineering Core Jobs CS R2008 CSE CSIR NET EBooks Download ECE EEE EIE Electives Electrical and Electronics Engineering Electronics and communication Electronics and Instrumentation Engineering Engineering Engineering Colleges in Maharashtra Engineering Colleges in TamilNadu Engineering Admissions Engineering Colleges Engineering Colleges in Karnataka Engineering Jobs Engineering Syllabus Entrance Exam Dates Entrance Exam Results Entrance Examination Exam Time Table Experiencer First Year Syllabus Freshers Full Time Jobs Government jobs in india Hardware and Networking Jobs Hotel Management and Catering Technology IGNOU Information Technology INTEVIEW QUESTIONS IT Jobs JNTU Question Papers Jobs in Bangalore Jobs in Chennai Jobs in Coimbatore Jobs in Delhi Jobs in Hyderabad Jobs in India Jobs in Kerala Jobs in Noida Jobs in Tamilnadu Jobs in TATA Karnataka Educations Lab Manuals Mechanical Engineering Medical Colleges Placement Papers Plus 2 Preparation for exams Private Jobs in India Question Papers Question Papers Download Results Announcement Semester 1 Semester 2 Semester 3 Semester 4 Semester 5 Semester 6 Semester 7 Semester 8 Syllabus Syllabus Download Tamil Movie TCS Placement Papers Teaching Jobs TECH MAHINDRA Textile Technology Top colleges University Results UPSC VICEVESVARAYA TECHNOLOGICAL UNIVERSITY waec Walk-in Interview Web Designers

Followers

Archive

Anna university Engineering Syllabus

Earn Money From Online

Government jobs in india

Admission Notification

Total Pageviews

 

Privacy Policy
http://topengineeringcollegesintamilnadu.blogspot.com use third-party advertising companies to serve ads when you visit our website. These companies may use information (not including your name, address, email address, or telephone number) about your visits to this and other websites in order to provide advertisements about goods and services of interest to you. If you would like more information about this practice and to know your choices about not having this information used by these companies, click here.