Accounting and Financial Management (3) Analog and Digital Communication (2) Artificial Intelligence (2) BE(Civil) (2) BE(CSE) (83) BE(ECE) (11) BE(Mech) (10) Business Processes (3) C# and .NET Framework (2) Communication Skills (1) Compiler Design (1) COMPONENT BASED TECHNOLOGY (1) COMPUTER ARCHITECTURE (1) COMPUTER GRAPHICS and MULTIMEDIA SYSTEMS (6) COMPUTER INTEGRATED MANUFACTURING (1) Computer Networks (9) Computer Organization (2) Computer Programming (1) Consumer Behaviour (1) Control Systems (1) Cryptography and Network Security (3) Datastructures and Algorithms (10) Datawarehousing and Mining (1) DBMS (5) DESIGN AND ANALYSIS OF ALGORITHMS (9) DESIGN OF MACHINE ELEMENTS (1) DIGITAL PRINCIPLES AND SYSTEMS DESIGN (3) Discrete Mathematics (1) DISTRIBUTED COMPUTING (2) DSP (8) DYNAMICS OF MACHINERY (2) Economic Foundations (1) ELECTRICAL ENGINEERING (1) ELECTRICAL ENGINEERING AND CONTROL SYSTEMS (1) Electromagnetic Fields (3) ELECTRONIC CIRCUITS (1) ELECTRONIC COMMERCE (4) ELECTRONIC DEVICES AND CIRCUITS (1) EMBEDDED SYSTEMS (1) FUNDAMENTALS OF COMPUTING (2) Graphics and Multimedia (3) HEAT AND MASS TRANSFER (1) HUMAN RESOURCE MANAGEMENT (1) Internet Programming (9) INTRODUCTION TO FINITE ELEMENT ANALYSIS (1) Legal Aspects of Business (1) MANAGEMENT INFORMATION SYSTEMS (1) Marketing Management (1) MATHEMATICAL FOUNDATIONS OF COMPUTER SCIENCE (4) MATHEMATICS - I (1) MBA (9) MCA (83) MCA QUESTION BANK (2) MECHATRONICS (1) MicroProcessor and Controllers (4) MICROPROCESSORS AND APPLICATIONS (5) MIDDLE WARE TECHNOLOGIES (3) MOBILE COMPUTING (5) NETWORK PROGRAMMING (1) NUMERICAL METHODS (1) OBJECT ORIENTED ANALYSIS AND DESIGN (5) Object Oriented Programming (18) Operating System (2) OPERATING SYSTEMS (9) Organizational Behaviour (2) POWER ELECTRONICS (1) Principles of Management (8) PROBABILITY AND QUEUEING THEORY (2) Probability and Statistics (1) PROBLEM SOLVING AND PROGRAMMING (2) PROCESS PLANNING AND COST ESTIMATION (1) PROFESSIONAL ETHICS AND HUMAN VALUES (1) RANDOM PROCESSES (1) RESOURCE MANAGEMENT TECHNIQUES (2) ROBOTICS (1) Security analysis (1) Service Marketing (1) SIGNALS AND SYSTEMS (1) Software Engineering (8) SOFTWARE PROJECT MANAGEMENT (4) SOFTWARE QUALITY MANAGEMENT (2) System Software (2) TCP/IP PROTOCOL SUITE (3) Theory of Computation (4) Total Quality Management (2) UNIX AND NETWORK PROGRAMMING (4) Visual Programming (2) WEB GRAPHICS (2) WEB TECHNOLOGY (2) XML AND WEB SERVICES (4)

Thursday, February 25, 2010

THEORY OF COMPUTATION APRIL/MAY 2008


B.E/B.Tech DEGREE EXAMINATION APRIL/MAY 2008
Fifth Semester
Computer Science and Engineering
(Regulation 2004)

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.
                                                                          

(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