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)

Tuesday, March 9, 2010

THEORY OF COMPUTATION


THEORY OF COMPUTATION

 PART A – (10 X 2 = 20 MARKS)


1. What is the difference between DFA and NFA?
2. Give regular set for the following expression: 1(01)*(10)*1
3. For the grammar G defined by S->AB, D->a,A->Aa,A->bB,B->Sb, give derivation tree for the sentential form babab
4. Give pumping lemma to prove that given language L is not context free.
5. Give formal definition of PDA.
6. Give an example of a language accepted by a PDA but not by DPDA.
7. Prove that the function f(n)=n-1 is computable.
8. Design a Turning machine to compute n mod 2.
9. What is undecidability?
10. Differentiate between recursive and recursively enumerable language.


PART B – (5 x 16 = 80 MARKS)


11. Construct a context free grammar for the given language L={anbn|/n>=1}U{amb2m/m>=1} and hence a PDA accepting L by empty stack (16)

12.a) Prove the equivalence of NFA and DFA. (8)
b) Prove that a balanced parenthesis is not a regular language. (8)

(OR)

12.a) Explain in detail with an example the conversion of NDFA to DFA (8)
b) Show that L = {an! : n>=0} is not regular. (8)

13.a) Explain in detail the ambiguity in context free grammar. (8)
b) Convert the grammar S->ABb|a, A->aaA|B, B->bAb into greibach normal form. (8)
(OR)

13.a) Construct a context free grammar for the languages L(G1)={aib2i/I>0} and L(G2)={anban/n>0} (8)
(b) Prove that {op | p is prime} is not context free. (8)

14. Construct a Turing Machine to do the proper subtraction (16)

(OR)

14.a) Construct a Turning machine to perform multiplication (8)
b) Prove the equivalence of two-way infinite tape with standard Turing machine. (8)

15.a) Discuss in detail about universal Turing machine. (8)
b) Prove that halting problem is undecidable. (8)

(OR)

15.a) Prove that the union and intersection of two recursive languages are also recursive. (8)
b) Prove that there exists an recursively enumerable language whose complement is not recursively enumerable. (8)



No comments:

Post a Comment