CS2357 OOAD (Object Oriented Analysis & Design) LAB MANUAL - Anna University Chennai

CS 2357 OOAD LAB MANUAL

III YEAR

 Department of Information Technology

DOWNLOAD AS PDF FILE

 

DOWNLOAD AS WORD FILE

 

 

 

 

 

CS2303 Theory of Computation (TOC) - Important Theorems & Questions

Anna University

Department of Computer Science Engineering and Information Technology

V Semester and VII Semester

Important Theorems

Semester: V
Year : 3rd Yr
Department : B.E Computer Science Engineering and B.Tech Information Technology
Regulation : 2008
Subject Code : CS2303
Subject Name : Theory of Computation
Contents : CS2303 Theory of Computation - Important Theorems.

CS2303 Theory of Computation

SOME OF THE IMPORTANT THEOREMS AND PROOFS

1. Proof by counter examples

2. Inductive proofs – problems

Extended del transition for NFA, DFA, sigma NFA

Language accepted by DFA < = > NFA

Refer Hopcroft book for below theorems

Pg : 77, theorem 2.11

Pg : 78, theorem 2.12

Theorem – 2.22, pg : 93

Theorem – 3.4, pg – 105

Pg – 116, theorem – 3.7

Pumping lemma for regular expression

Proof for pumping lemma

Applications for pumping lemma

Closure properties of regular expression page: 140

Theorems: 5.12, 5.14, 5.16

Page - 199 – theorem

Applications of CFG

PDA – definition, instantaneous description of PDA

Page: 245 - theorem - 6.9

Page: 248 - theorem – 6.11

1st unit – equivalent DFA and NFA, NFA with and without sigma transition

2nd unit – DFA to regular expressions and regular expressions to DFA , pumping lemma , properties of regular expression

3rd unit – refer above

Equivalent of CFG to PDA and PDA to CFG, deterministic properties of CFG

CNF and GNF - problem s and proofs

5th unit Theorems

1. Recursive language and recursive enumerable language

2. Decision problems and undecidable problems examples

3. Properties of recursive languages and recursive enumerable language

(4 theorems – 16 marks) (in boxes they will give )

4. Define diagonal language

5. Universal language – based theorems

6. Rice theorems

7. PN and NP problems

8. Samples for NP problems

9. NP – complete, NP – hard

Sample NP - complete and NP – hard problems

10. Binary equivalent of following integers is stored in a tape

Multiply the following by 2

(11 x 12 = 1100)

(100 x 10 = 1000)

11. Define diagonal language

12. Define the language LU and show that

LU is recursively enumerable but not recursive

13. Multiple track TM and multiple tape TM difference

14. Minimum no of stacks to represent a TM and for PDA

15. Count down M/C

16. Properties of CFL, properties of regular language

17. Final stack , empty stack – 2 theorems and proof of it

18. CFG – equivalent PDA - proof and theorems

19. PDA ? CFG ( theorem )

20. Pumping lemma – proof – 8 marks for CFL and regular language, problems( 4m / 2m )

 

CS 2352 — PRINCIPLES OF COMPILER DESIGN (POCD) Important Questions - Anna University

Anna University

B.E./B.Tech. DEGREE EXAMINATION, APRIL/MAY 2011

Sixth Semester

Computer Science and Engineering

CS 2352 — PRINCIPLES OF COMPILER DESIGN

(Regulation 2008)

---

Time : Three hours
Maximum : 100 marks
Answer ALL questions

---

PART A — (10 × 2 = 20 marks) 1. What is an interpreter?
2. Define token and lexeme.
3. What is handle pruning?
4. What are the limitations of static allocation?
5. List out the benefits of using machine-independent intermediate forms.
6. What is a syntax tree? Draw the syntax tree for the following statement:
. : c b c b a − ∗ + − ∗ =
7. List out the primary structure preserving transformations on basic block.
8. What is the purpose of next-use information?
9. Define dead-code elimination.
10. What is loop optimization?

---

PART B — (5 × 16 = 80 marks) 11. (a) (i) Describe the various phases of complier and trace the program
segment 4 : ∗ + = c b a for all phases. (10)

(ii) Explain in detail about compiler construction tools. (6)
Or
(b) (i) Discuss the role of lexical analyzer in detail. (8)
(ii) Draw the transition diagram for relational operators and unsigned
numbers in Pascal. (8)

12. (a) (i) Explain the error recovery strategies in syntax analysis. (6)
(ii) Construct a SLR construction table for the following grammar.
T E E + →
T E →
F T T ∗ →
F T →
( ) E F →
id F → (10)

Or
(b) (i) Distinguish between the source text of a procedure and its
activation at run time. (8)

(ii) Discuss the various storage allocation strategies in detail. (8)
13. (a) (i) Define three-address code. Describe the various methods of implementing three-address statements with an example. (8)

(ii) Give the translation scheme for converting the assignments into
three address code. (8)
Or
(b) (i) Discuss the various methods for translating Boolean expression. (8)

(ii) Explain the process of generating the code for a Boolean expression in a single pass using back patching. (8)
132  132  132 
11267 3

14. (a) (i) Write in detail about the issues in the design of a code generator. (10)
(ii) Define basic block. Write an algorithm to partition a sequence of
three-address statements into basic blocks. (6)

Or

(b) (i) How to generate a code for a basic block from its dag
representation? Explain. (6)
(ii) Briefly explain about simple code generator. (10)


15. (a) (i) Write in detail about function-preserving tran
sformations. (8)
(ii) Discuss briefly about Peephole Optimization. (8)
Or

(b) (i) Write an algorithm to construct the natural loop of a back edge. (6)
(ii) Explain in detail about code-improving transformations. (10)
 

CS2352 PRINCIPLES OF COMPILER DESIGN (POCD)2012 Important Questions

Anna University

PRINCIPLES OF COMPILER DESIGN 2012 Important Questions

Subject Code : CS2352
Subject Name : Principles Of Compiler Design

Unit I
1. Describe the various phases of compiler and trace it with the program segment (position:= intial+rate *60)

2. Explain in detail about compiler constructions tools.

3. Explain in detail about the role of lexical analyzer.

4. Explain briefly in detail about the Input buffering technique with the algorithm.

5. Explain in detail about the cousins of compiler


Unit II

1. Construct predictive parsing table for the grammar
   

2. Construct the predictive parser for the following grammar and
Construct the behavior of the parser on the sentence (a,a) using the
grammar
   

3. Construct the SLR Parser for the following grammar with an
appropriate algorithm
   

4. Construct the SLR Parser for the following grammar and Construct the behavior of the parser on the sentence (a,a) using the grammar
   

5. Construct the SLR Parser for the following grammar with an appropriate algorithm
   


Unit III

1. Define three- address code. Describe the various types &methods of implementing three — address statements with an example.

2. What are the various data structure used for symbol table construction
and explain in detail.

3. How can Back Patching be used to generate code for Boolean expressions & construct the annotated parse tree with the translation
scheme?

4. Discuss the various methods for translating Boolean expression.

Unit IV

1. Briefly explain about simple code generator.

2. Define basic block. Write an algorithm to partition a sequence of three address statements into basic blocks

3. Construct the DAG for the following basic block:
d:=b*c e:=a+b b:=b*c a:=e-d

4. Write in detail about the issues in the design of a code generator.

Unit V

1. Write in detail about function — preserving transformations & loop optimizations.

2. Explain in detail about code- improving transformations.

3. Describe in detail about principal sources of optimization.

4. Explain in detail optimization of basic blocks with example.

5. Discuss briefly about peephole optimization.