October 31, 2011

CS1303 THEORY OF COMPUTATION question papers Previous Year Anna university question papers Download


B.E/B.Tech DEGREE EXAMINATION APRIL/MAY 2008
Fifth Semester
Computer Science and Engineering
CS1303—THEORY OF COMPUTATION
(Regulation 2004)
Time: 3 hours                                                                  Maximum marks: 100
Answer ALL questions

PART A (10 x 2 =20 marks)


1.Define Automaton?

2.What is the principle of mathematical Induction?

3.Construct a DFA for the regular expression aa*/bb*..

4.Construct a DFA over ∑=(a,b) which produces not more than 3 a’s.

5.Let S-> aB/bA

                  A->aS/bAA/a
                  B->bS/aBB/b
      Derive the string aaabbabba as left most derivation.

6. What is meant by empty production removal in PDA.?

7.State the Pumping lemma for CFG.

8.   Define turing machine

9.What is meant by halting problem.

10.What is post correspondence problem?

PART B (5 x 16 = 80)
11.  (a )  (i) Prove that for every integer n>=0 the number 42n+13n+2  is a multiple of 13

(ii)construct a DFA that will accept strings on{a,b}where the number of b’s divisible by 3
(or)
(b)  (i)  Construct a finite automaton that accepts the set of all strings in {a,b,c}* such that the last symbol in input string appears earlier in the string

12 (a)  (i)   Construct the regular expression to the transition diagram.  
                                                                             
Diagram
(or)
(b)Construct a NFA for regular expression (a/b)*abb and draw its equivalent DFA.

13. (a) Construct a  CFG accepting  L={ambn/n
(or)
(b)Convert the grammar with productions into CNF  A->Bab/λ.

14.(a) Design a deteministic turing machine to accept the language L={aibici/i>=0} 
(or)
14. (b)Determine whether the language given byL={An2/N>=1} is a context free or not.                    

15. (a)Prove that the function fadd (x,y)=x+y
is a primitive recursive
(or)
15. (b)Show there exists aTM for which the halting problem is unsolvable      

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

 

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.