CS2253 Computer Organization and Architecture - Most Important Questions 2014 Edition

CS2253 Computer Organization and Architecture - Most Important Questions 2014 Edition

Anna University , Chennai

computer Science Engineering Department 

II Year CSE – IV sem

CS2253 Computer Organization and Architecture

Most Important Questions – 2014 Edition

Unit 1

1. Explain the Differences between CISC & RISC
2. Explain the various Instruction types?
3. Write in detail about various addressing modes.
4. Explain the various generations of Computer
5. Explain the Booth’s algorithm for multiplication of signed two’s Complement numbers.                               6. Explain the multiple bus organization in detail.
7. Explain the floating point addition and subtraction
8. State the Non – restoring division technique
9. Draw and explain the flowchart of floating point addition process
10. Explain with a diagram the designs of a fast multiplier using carry save Adder circuit .Give the block diagram for a floating point adder / sub tractor unit and discuss its operation

UNIT 2

1. Explain the concept of hardwired control unit (16)
2. Explain the concept of micro programmed control unit (16)
3. a. Sketch and explain the multiple bus organization (8)
b. Explain the execution of complete instruction (8)
4. Explain in detail about nano-programming (16)

UNIT 3

1. Describe in detail about pipeline processing. (16)
2. a. Explain in detail about data hazards (10)
b. Briefly explain about different types of exception. (6)
3. Explain in detail about instruction hazards (16)
4. Explain in detail about the following
a) Influence on instruction set (8)
b) Data path considerations (8)

UNIT 4

1. Illustrate the characteristics of some common memory technologies. (16)
2. (a)Describe in detail about associative memory. (8)
(b) Comparing paging and segmentation mechanisms for implementing the virtual memory. (8)
3. What is Memory Interleaving? Explain the addressing of multiple modules Memory system. (16)
4. Discuss the different mapping techniques used in cache memories and their relative merits and demerits. (16)
5. What do you mean by virtual memory? Discuss how paging helps in implementing virtual memory. (16)
6. (a) Discuss any six ways of improving the cache performance. (8)
(b) Illustrate memory read and write operation. (8)

UNIT 5 

1. Explain with the block diagram the DMA transfer in a computer System. (16)
2. (a) Describe in detail about IOP organization. (8)
(b) Describe the data transfer method using DMA. (8)
3. Write short notes on the following
(a) Magnetic disk drive (8)
(b) Optical drives (8)
4. Discuss the design of a typical input or output interface. (16)
5. What are interrupts? How are they handled? (16)

Anna University - Nov / Dec 2013 Exam Results Announced

Anna University , Chennai

Controller of Examination

Nov / Dec 2013 Exam Results - 3rd , 5th and 7th Semester Results

UG / PG Nov. Dec. 2013 Exam Results chennai/Madurai 

UG / PG Nov. Dec. 2013 Coimbatore Results 

UG / PG Nov. Dec. 2013 Trichy Results 

UG / PG Nov. Dec. 2013 Marks System Results 

Anna University Link :
http://coe1.annauniv.edu
http://coe2.annauniv.edu

Check Your Results Via SMS :

-> For CHENNAI/MADURAI Students :
ANBECN<SPACE>REGNO<SEND>56767999

-> For COIMBATORE Students :
ANBECB<SPACE>REGNO<SEND>56767999

-> For TRICHY Students :
ANBETI<SPACE>REGNO<SEND>56767999

read more

CS 2305 Programming Paradigms Anna University Important Questions 2 marks and 16 marks questions | CS2305 important questions from all 5 units for 5th semester CSE dpt ...

CS 2305 Programming Paradigms Anna University Important Questions 2 marks and 16 marks questions | CS2305 important questions from all 5 units for 5th semester CSE dpt ... 

**we will update the important questions and topics soon ..here we have listed the repeated questions asked in AU question Papers** 

CLICK HERE TO DOWNLOAD CS2305 PP IMPORTANT QUESTIONS

CS2305 Programming Paradigms

UNIT I

PART A

1.      What are the OOP Principles?

2.      What is Encapsulation?

3.      What is Polymorphism?

4.      What is Inheritance?

5.      What are the features of Java Language?

6.      What is the need for Java Language?

7.      What is platform independency?

8.      What is Architecture Neutral?

9.      How Java supports platform independency?

10.  Why Java is important to Internet?

11.  What are the types of programs Java can handle?

12.  What is an applet program?

13.  Compare Application and Applet.

14.  What are the advantages of Java Language?

15.  Give the contents of Java Environment (JDK).

16.  Give any 4 differences between C and Java.

17.  Give any 4 differences between C++ and Java.

18.  What are the different types of comment symbols in Java?

19.  What are the data types supported in Java?

20.   What is the difference between a char in C/C++ and char in Java?

21.   How is a constant defined in Java?

22.   What is the use of final keyword?

23.   What are the different types of operators used in Java?

24.   What is short-Circuit operator?

25.  What is labeled break?

26.  What is the use of for each control structure?

27.  What is the need for static variables?

28.  What is the need for static methods?

29.  Compare static constants and final constants.

30.  Why is main method assigned as public?

31.  Why is main method assigned as static?

32.  What are the types of variables Java handles?

33.  What are the relationships between classes?

34.  What is the general form of a class?

35.  What is the use of new keyword?

36.  If ObjA1 is an object of class A created using new keyword, What does the statement A ObjA2=ObjA1;    mean?

37.  What is a constructor?

38.  What is the difference between a constructor and a method?

39.  What is the use of this keyword?

40.  What are destructors?

41.  How is object destruction done in Java?

42.  What is Garbage collection?

43.  What is the use of finalize method?

44.  Compare Garbage collection and finalize method?

45.  How is it guaranteed that finalize methods are called?

46.  What is method overloading?

47.  What is a String in Java?

48.  What is the difference between a String in Java and String in C/C++?

49.  Name a few String methods.

50.  What is the difference between Concat method and + operator to join strings?

51.  What is String Buffer?

52.  How does String class differ from the String Buffer class?

53.  Name some methods available under String Buffer class.

54.  Output of some expressions using String methods.

55.  How will you initialize arrays?

56.  What is arraycopy method? Explain with syntax.

57.  What are the methods under Util.Arrays?

58.  Use the array sort method to sort the given array.

59.  Give the syntax for array fill operation.

60.  What is vector? How is it different from an array?

61.  What is the constraint for using vectors?

62.  What is wrapper class?

63.  What are the different access specifiers available in Java?

64.  What is the default access specifier in Java?

65.  What is a package in Java?

66.  Name some Java API Packages.

67.  Name some JavaDoc Comments.

68.  What is CommandLine Arguments.

Part B

1.      Explain OOP Principles.

2.      Explain the features of Java Language.

3.      Compare and Contrast Java with C.

4.      Compare and Contrast Java with C++.

5.      Explain Constructors with examples.

6.      Explain the methods available under String and String Buffer Class.

7.      Explain the Date Class methods with examples.

8.      Discuss in detail the access specifiers available in Java.

9.      Explain the different visibility controls and also compare with each of them.

10.  Explain the different methods in java.Util.Arrays class with example.

11.  Explain Packages in detail.

12.  Discuss the methods under Array Class.

13.  Discuss some of the classes available under Lang package.

14.  Illustrate with examples: static and final.

15.  Explain method overriding with example program.

16.  What is javaDoc? Explain the comments for classes, methods, fields and link.

17.  Application Programs in Java.

UNIT II

PART A

1. Define Inheritance
2. What are the types of inheritance?
3. How is multiple inheritance achieved in java?
4. What is the use of super keyword?
5. What are object wrappers? Give example.
6. What is Inheritance Hierarchy?
7. Differentiate overloading and overriding.
8. Define polymorphism.
9. Differentiate static binding and dynamic binding.
10. When will a class be declared as final?
11. When will a method be declared final?
12. What is an abstract class?
13. What is the need for abstract classes?
14. Explain about protected visibility control.
15. What are the methods under "object" class / java.lang.Object.
16. Explain toString method of object class.
17. What is reflection?
18. What are the uses of reflection in Java.
19. How will you create an instance of Class.
20. What are the methods under reflection used to analyze the capabilities of classes?
21. How to create arrays dynamically using reflection package.
22. Define an interface.
23. What is the need for an interface?
24. What are the properties of an interface?
25. Differentiate Abstract classes and interface.
26. What is object cloning?
27. Differentiate cloning and copying.
28. Differentiate shallow copy and deep copy in cloning.
29. Does Inheritance removes any fields/or methods of super class?
30. Mention the use of final keyword.
31. What is nested class? Mention its types.
32. What is inner class?
33. What is the need for inner classes?
34. What are the rules for inner class?
35. What is local inner class and anonymous inner class? Give their advantages.
36. Write the advantages and disadvantages of static nested class.
37. Define proxies.
38. Write the application of proxies.
39. What are the properties of proxy classes?

PART B

1.      Explain the concept of inheritance and its types.

2.      Explain the concept of overriding with examples.

3.      What is dynamic binding? Explain with example.

4.      Explain the uses of reflection with examples.

5.      Define an interface. Explain with example.

6.      Explain the methods under “object” class and “class” class.

7.      What is object cloning? Explain deep copy and shallow copy with examples.

8.      Explain static nested class and inner class with examples.

9.      With an example explain proxies.

10.  Develop a message abstract class which contains playMessage abstract method. Write a different sub-classes like TextMessage, VoiceMessage and FaxMessage classes for to implementing the playMessage method.

11.  Develop a abstract Reservation class which has Reserve abstract method. Implement the sub-classes like ReserveTrain and ReserveBus classes and implement the same.

12.  Develop an Interest interface which contains simpleInterest and compInterest methods and static final field of Rate 25%. Write a class to implement those methods.

13.  Develop a Library interface which has drawbook(), returnbook() (with fine), checkstatus() and reservebook() methods. All the methods tagged with public.

14.  Develop an Employee class which implements the Comparable and Cloneable interfaces. Implement the sorting of persons (based on name in alphabetical). Also implement the shallow copy (for name and age) and deep copy (for DateOfJoining). 

15.  Explain the different methods supported in Object class with example.

16.  Explain the methods supported in Class class.

17.  Explain the Methods supported in reflect package. Also write a program to implement the reflection of a particular class details like constructors, methods and fields with its modifiers.

18.  Develop a static Inner class called Pair which has MinMax method for finding min and max values from the array.

19.  What is proxy class? Develop a code for constructing a proxy objects to trace a binary search method with explanations.                   

UNIT III

PART A

1. Draw the inheritance hierarchy for the frame and component classes in AWT and Swing.
2. What are the advantages of using swing over awt?
3. How do achieve special fonts for your text? Give example.
4. Give the syntax of drawImage() and copyArea() methods.
5. What is Adapter class?
6. Draw the AWT event Hierarchy.
7. What are the swing components?
8. What are the methods under Action Interface.
9. What are the methods under WindowListener Interface.
10. What is the difference between Swing and AWT?

PART B

1. Explain the classes under 2D shapes.
2. Explain event handling with examples.
3. Explain action event with an example.
4. What are the swing components. Explain.
5. Describe the AWT event hierarchy.

UNIT IV

PART A

1.      What is generic programming?

2.      What are Checked and UnChecked Exception?

3.      What are checked exceptions?

4.      What are runtime exceptions?

5.      What is the difference between error and an exception?

6.      What classes of exceptions may be caught by a catch clause?.

7.      If I want an object of my class to be thrown as an exception object, what should I do?

8.      How to create custom exceptions?

9.      What are the different ways to handle exceptions?

10.  What is the purpose of the finally clause of a try-catch-finally statement?

11.  What is the basic difference between the 2 approaches to exception handling.
Is it necessary that each try block must be followed by a catch block?

12.  How does Java handle integer overflows and underflows?

PART B

1.      Explain generic classes and methods.

2.      Explain exception hierarchy.

3.      What are the advantages of Generic Programming?

4.      Explain the different ways to handle exceptions.

5.      How Java handle overflows and underflows?

UNIT V

PART A

1. Describe synchronization in respect to multithreading.
2. Explain different way of using thread?
3. What is synchronization and why is it important?
4. When a thread is created and started, what is its initial state?
5. What are synchronized methods and synchronized statements?
6. What is daemon thread and which method is used to create the daemon thread?
7. What method must be implemented by all threads?
8. What kind of thread is the Garbage collector thread?
9. What is a daemon thread?
10. What is a thread?
11. What is the algorithm used in Thread scheduling?
12. What are the different level lockings using the synchronization keyword? 
13. What are the ways in which you can instantiate a thread?
14. What are the states of a thread?
15. What are the threads will start, when you start the java program?
16. What are the different identifier states of a Thread?
17. Why do threads block on I/O?
18. What is synchronization and why is it important?

PART B

1. Explain the different states of a thread.
2. Explain thread synchronization with examples.
3. Explain the algorithm used for thread scheduling.
4. Describe multi threading.
5. Explain Deadlocks.

read more

CS 2303 Theory of Computation (TOC) Anna University Important Questions 2 marks and 16 marks questions | CS2303 important questions from all 5 units for 5th semester CSE dpt ...

CS 2303 Theory of Computation (TOC) Anna University Important Questions 2 marks and 16 marks questions | CS2303 important questions from all 5 units for 5th semester CSE dpt ... 

**we will update the important questions and topics soon ..here we have listed the repeated questions asked in AU question Papers** 

CLICK HERE TO DOWNLOAD CS2303 TOC IMPORTANT QUESTIONS

 CS2303 Theory of Computation

UNIT-I AUTOMATA 

PART-A(2-MARKS) 

1 List any four ways of theorem proving. 
2 Define Alphabets. 
3 Write short notes on Strings. 
4 What is the need for finite automata? 
5 What is a finite automaton? Give two examples. 
6 Define DFA. 
7 Explain how DFA process strings. 
8 Define transition diagram. 
9 Define transition table. 
10. Define the language of DFA. 
11. Construct a finite automata that accepts {0,1}+. 
12. Give the DFA accepting the language over the alphabet 0,1 that have the set of   
            all strings ending in 00. 
13. Give the DFA accepting the language over the alphabet 0,1 that have the set of 
            all strings with three consecutive 0’s. 
14. Give the DFA accepting the language over the alphabet 0,1 that have the set of 
            all strings with 011 as a substring. 
15. Give the DFA accepting the language over the alphabet 0,1 that have the set of 
            all strings whose 10th symbol from the right end is 1. 
16. Give the DFA accepting the language over the alphabet 0,1 that have the set of 
             all strings such that each block of 5 consecutive symbol contains at least two 
              0’s. 
17. Give the DFA accepting the language over the alphabet 0,1 that have the set of 
             all strings that either begins or end(or both) with 01. 
18. Give the DFA accepting the language over the alphabet 0,1 that have the set of 
            all strings such that the no of zero’s is divisible by 5 and the no of 1’s is 
             divisible by 3. 
19. Find the language accepted by the DFA given below. 
20. Define NFA. 
21. Define the language of NFA. 
22. Is it true that the language accepted by any NFA is different from the regular  
language? Justify your Answer. 
23. Define ε-NFA. 
24. Define ε closure. 
25. Find the εclosure for each state from the following automata. 


Part B

1. a) If L is accepted by an NFA with ε-transition then show that L is accepted by an  
      NFA without ε-transition. 
b) Construct a DFA equivalent to the NFA.
M=({p,q,r},{0,1}, δ,p,{q,s})
Where δis defined in the following table.

δ 0 1 
p {q,s} {q} 
q {r} {q,r} 
r {s} {p} 
s - {p} 
2. a)Show that the set L={an bn/n>=1} is not a regular. (6) b)Construct a DFA equivalent to the NFA given below: (10) 
0 1 
p {p,q} P 
q r R 
r s -
s s S 

3. a)Check whether the language L=(0n 1n /n>=1) is regular or not? Justify your answer. 
b) Let L be a set accepted by a NFA then show that there exists aDFA that accepts L. 
4. Define NFA with ε-transition. Prove that if L is accepted by an NFA with ε-transition then L is also accepted by a NFA without ε-transition. 
5. a) Construct a NDFA accepting all string in {a,b}+ with either two consecutive a’s or two consecutive b’s. 
b) Give the DFA accepting the following language:set of all strings beginning with a 1 that when interpretedas a binary integer is a multiple of 5.
6. Draw the NFA to accept the following languages. 
(i) Set of Strings over alphabet {0,1,…….9} such that the final digit has  
     appeared before. (8) 
      (ii)Set of strings of 0’s and 1’s such that there are two 0’s separated by a number of        positions that is a multiple of 4. 
7.a)Let L be a set accepted by an NFA.Then prove that there exists a deterministic finite automaton that accepts L.Is the converse true? Justify your answer. (10) 
b)Construct DFA equivalent to the NFA given below: (6) 

8.a) Prove that a language L is accepted by some ε–NFA if and only if L is accepted by some DFA. (8) 
b) Consider the following ε–NFA.Compute the ε–closure of each state and find it’s equivalent DFA. (8) 
ε A b C 
p {q} {p} Ф Ф 
q {r} ф {q} Ф 
*r Ф ф ф {r} 

9.a) Prove that a language L is accepted by some DFA if L is accepted by some NFA. 
b) Convert the following NFA to it’s equivalent DFA 
0 1 
p {p,q} {p} 
q {r} {r} 
r {s} ф 
*s {s} {s} 

10.a) Explain the construction of NFA with εtransition from any given regular expression. 
b) Let A=(Q,∑, δ, q0 ,{qf ) be a DFA and suppose that for all a in ∑wehave δ(q0, a)= δ(qf ,a). Show that if x is a non empty string in L(A),then for all k>0,xk is also in L(A). 


UNIT-II REGULAR EXPRESSIONS AND LANGUAGES 
PART-A 
1 Define Regular expression. Give an example. 
2 What are the operators of RE. 
3 Write short notes on precedence of RE operators. 
Write Regular Expression for the language that have the set of strings over  
{a,b,c} containing at least one a and at least one b. 
4 Write Regular Expression for the language that have the set of all strings of 0’s 
5 and 1’s whose 10th symbol from the right end is 1. 
6 Write Regular Expression for the language that has the set of all strings of 0’s 
             and 1’s with at most one pair of consecutive 1’s. 
7 Write Regular Expression for the language that have the set of all strings of 0’s 
8 and 1’s such that every pair of adjacent 0’s appears before any pair of adjacent 
9 1’s. 
10 Write Regular Expression for the language that have the set of all strings of 0’s   
             and 1’s whose no of 0’s is divisible by 5. 
11 Write Regular Expression for the language that has the set of all strings of 0’s 
             and 1’s not containing 101 as a substring. 
12 Write Regular Expression for the language that have theset of all strings of 0’s    
            and 1’s such that no prefix has two more 0’s than 1’s, not two more 1’s than    
             0’s. 
13.      Write Regular Expression for the language that have the set of all   
            strings of 0’s and 1’s whose no of 0’s is divisible by 5 and no of 1’s is  
            even. 
14. Give English descriptions of the languages of the regular expression (1+ ε)(00*1)*0*. 
15. Give English descriptions of the languages of the regular expression (0*1*)*000(0+1)*. 
16. Give English descriptions of the languages of the regular expression (0+10)*1*. 
17.      Convert the following RE to ε-NFA.01*.

18.      State the pumping lemma for Regular languages. 
19. What are the application of pumping language? 
20. State the closure properties of Regular language. 
21. Prove that if L and M are regular languages then so is LUM. 
22. What do you mean by Homomorphism? 
            Suppose H is the homomorphism from the alphabets {0,1,2} to the alphabets  
           {a,b} defined by h(0)=a h(1)=ab h(2)=ba. What is h(0120) and h(21120). 
23. Suppose H is the homomorphism from the alphabets {0,1,2} to the alphabets   
           {a,b} defined by h(0)=a h(1)=ab h(2)=ba. If L is the language L(01*2) what is   
            h(L). 

24. Let R be any set of regular languages is U Ri regular?Prove it. 
25. Show that the compliment of regular language is also regular. 
26 . What is meant by equivalent states in DFA. 


PART-B 
1.a)Construct an NFA equivalent to (0+1)*(00+11) 
2.a)Construct a Regular expression corresponding to the state diagram given in the following figure. 

b) Show that the set E={0i 1i |i>=1} is not Regular. (6) 
3.a)Construct an NFA equivalent to the regular expression (0+1)*(00+11)(0+1)*. 
b)Obtain the regular expression that denotes the language accepted by the following DFA. 

4.a)Construct an NFA equivalent to the regular expression ((0+1)(0+1)(0+1))* 
   b)Construct an NFA equivalent to 10+(0+11)0*1 
5.a)Obtain the regular expression denoting the language accepted by the following DFA (8) b)Obtain the regular expression denoting the language accepted by the following DFA by using the formula Rij k 


6. a)Show that every set accepted by a DFA is denoted by a regular Expression 
b)Construct an NFA equivalent to the following regular expression01*+1. 
7. a)Define a Regular set using pumping lemma Show that the language L={0i2 / i is an integer,i>=1} is not regular 
b)Construct an NFA equivalent to the regular expression 10+(0+11)0*1 
8. a) Show that the set L={On2/n is an integer,n>=1} is not regular. 
b)Construct an NFA equivalent to the following regular expression ((10)+(0+1) * 01. (10) 9.a)Prove that if L=L(A) for some DFA A,then there is a regular expression R such that L=L(R). 
b) Show that the language {0p,p is prime} is not regular. 
 10.Find whether the following languages are regular or not. 
(i) L={w ε{a,b}|w=wR}. 
(ii) L={0n 1m 2n+m,n,m>=1} 
(iii) L={1k|k=n2,n>=1} . (4) 
(iv) L1/L2={x | for some y εL2,xy εL1},where L1 and L2 are any two languages and L1/L2 is the quotient of L1 and L2. 
11.a) Find the regular expression for the set of all strings denoted by R213 from the deterministic finite automata given below: 

b)Verify whether the finite automata M1 and M2 given below are equivalent over {a,b}. 
12.a)Construct transition diagram of a finite automaton corresponding to the regular expression (ab+c *)*b.  

13.a)Find the regular expression corresponding to the finite automaton given below.  

b)Find the regular expression for the set of all strings denoted by R223 from the deterministic finite automata given below. 

14.a) Find whether the languages {ww,w is in (1+0)*} and {1k | k=n2 , n>=1} are regular or not. 
b) Show that the regular languages are closed under intersectionand reversal. 

UNIT-III CONTEXT FREE GRAMMARS AND LANGUAGES 
PART-A 
1. Define CFG.2.Find L(G)where G=({S},{0,1},{S->0S1,S->ε},S).
2. Define derivation tree for a CFG(or)Define parse tree.
3. Construct the CFG for generating the language L={an bn /n>=1}. 
4. Let G be the grammar S->aB/bA,A->a/aS/bAA,B->b/bS/aBB.for the string 
    aaabbabbba find the left most derivation. 
5. Let G be the grammar S->aB/bA,A->a/aS/bAA,B->b/bS/aBB.obtain parse tree for    the string aaabbabbba. 
6. For the grammar S->aCa,C->aCa/b.Find L(G). 
7. Show that id+id*id can be generated by two distinct leftmost derivation in the 
     grammar E->E+E | E*E | (E) | id . 
8. For the grammar S->A1B,A->0A | ε, B-> 0B | 1B| ε,give leftmost and rightmost   derivations for the string 00101. 
9. Find the language generated by the CFG G=({S},{0,1},{S->0/1/ ε,
 S->0S0/1S1},S). 
10 obtain the derivation tree for the grammar G=({S,A},{a,b},P,S) where P    
            consist of S->aAS / a, A->SbA / SS / ba. 
11 Consider the alphabet ∑={a,b,(,),+,*, ., ε} .Construct the context free grammar 
            that generates all strings in ∑* that are regular expression over the alphabet  
            {a,b}. 
12 Write the CFG to generate the set {am bn cp | m + n=p and p>=1}. 
13 Construct a derivation tree for the string 0011000 using the grammar 
S->A0S |0 | SS , A-> S1A | 10. 
14 Give an example for a context free grammar. 
15 Let the production of the grammar be S-> 0B | 1A, A-> 0 | 0S | 1AA, 
B-> 1|1S | 0BB.for the string 0110 find the right most derivation. 
16 What is the disadvantages of unambiguous parse tree. Give an example. 
17 Give an example of PDA. 
18. Define the acceptance of a PDA by empty stack. Is it true that the language accepted by a PDA by empty stack or by that of final state are different languages. 
20 What is additional featurePDA has when compared with NFA? Is PDA superior over NFA in the sense of language acceptance? Justify your answer. 
21. Explain what actions take place in the PDA by the transitions (moves) 
δ(q,a,Z)={(p1,γ1),(p2, γ2),…..(pm, γm)} and δ(q, ε,Z)= {(p1,γ1),(p2,  
γ2),…..(pm,γm)}.
22. What are the different ways in which a PDA accepts the language? Define them. Is a true that non deterministic PDA is more powerful than that of deterministic 
PDA? Justify your answer. 
23. Explain acceptance of PDA with empty stack. 
24. Is it true that deterministic push down automata and non deterministic push 
down automata are equivalent in the sense of language of acceptances? Justify your answer. 
25. Define instantaneous description of a PDA. 
26. Give the formal definition of a PDA. 
27. Define the languages generated by a PDA using final state of the PDA and 
empty stack of that PDA. 
28. Define the language generated by a PDA using the two methods of accepting a 
language. 
29. Define the language recognized by the PDA using empty stack. 

PART-B 
1. a) Let G be a CFG and let a=>w in G. Then show that there is a leftmost   
      derivation of w. 
b) Let G=(V,T,P,S) be a Context free Grammar then prove that if S=> αthen there is a      
            derivation tree in G with yield α.  
2. Let G be a grammar s->OB/1A, A->O/OS/1AA, B->1/1S/OBB. For the string     00110101 find its leftmost derivation and derivation tree. 
3)   a) If G is the grammar S->Sbs/a, Show that G is ambiguous. 
       b) Give a detailed description of ambiguity in Context free grammar 
4. a) Show that E->E+E/E*E/(E)/id is ambiguous. (6) b)Construct a Context free grammar G which accepts N(M), where M=({q0, q1},{a,b},{z0,z},δ,q0,z0,Φ) and where δis given by 
δ(q0,b,z0)={(q0,zz0)}
δ(q0, ε,z0)={(q0, ε)}
δ(q0,b,z)={(q0,zz)}
δ(q0,a,z)={(q1,z)}
δ(q1,b,z)={(q1, ε)}
δ(q1,a,z0)={(q0,z0)} 
5. a)If L is Context free language then prove that there exists PDA M such that L=N(M). 
b)Explain different types of acceptance of a PDA.Are they equivalent in sense of language acceptance? Justify your answer. 

6. Construct a PDA accepting {anbman/m,n>=1} by empty stack. Also construct   the  corresponding context-free grammar accepting the same set. 
7. a) Prove that L is L(M2 ) for some PDA M2 if and only if L is N(M1) for some PDA M1. 
     b)Define deterministic Push Down Automata DPDA. Is it true that DPDA and PDA are equivalent in the sense of language acceptance is concern? Justify Your answer. 
8.a) Construct a equivalent grammar G in CNF for the grammar G1 where G1 =({S,A,B},{a,b},{S->bA/aB,A->bAA/aS/a, B->aBB/bS/b},S)

b)Find the left most and right most derivation corresponding to the tree. 


9. a) Find the language generated by a grammar
 G=({S},{a,b},{S->aSb, S->ab},S) (4) 
b) Given G=({S,A},{a,b},P,S) where P={S->AaS|S|SS,A->SbA|ba}
 S-Start symbol. Find the left most and right most derivation of the string      
 w=aabbaaa. Also construct the derivation tree for the string w. 
c) Define a PDA. Give an Example for a language accepted byPDA by empty stack. 
10. G denotes the context-free grammar defined by the  
          following rules. ` S->ASB/ab/SS A->aA/A ,B->bB/A
    (i)Give a left most derivation of aaabb in G. Draw the associated parse tree.
   (ii)Give a right most derivation of aaabb in G. Draw the associated 
parse tree. 
   (iii) Show that G is ambiguous. Explain with steps. 
    (iv) Construct an unambiguous grammar equivalent to G. Explain.

11 a)   Construct the grammar for the following PDA. 
M=({q0, q1},{0,1},{X,z0},δ,q0,Z0,Φ) and where δis given by 
δ(q0,0,z0)={(q0,XZ0)}, δ(q0,0,X)={(q0,XX)},δ(q0,1,X)={(q1, ε)}, δ(q1,1,X)={(q1, ε)},δ(q1, ε,X)={(q1, ε)}, δ(q1, ε, Z0 )={(q1, ε)}. (12)
      b)  Prove that if L is N(M1) for some PDA M1 then L is L(M2 ) for somePDA M2. 
12.a)  Construct a PDA that recognizes the language 
{ai bj ck| i,j,k>0 and i=j or i=k}. 
b) Discuss about PDA acceptance 
(1) From empty Stack to final state. 
(2) From Final state to Empty Stack.

UNIT-IV PROPERTIES OF CONTEXTFREE LANGUAGES
PART-A

1 Define multitape Turing Machine. 
2 Explain the Basic Turing Machine model and explain in one move.What are the actions take place in TM?
3 Explain how a Turing Machine can be regarded as a computing device to compute integer functions. 
4 Describe the non deterministic Turing Machine model. Is it true the non deterministic Turing Machine model’s are more powerful than the basic Turing Machines? (In the sense of language Acceptance). 
5 Explain the multi tape Turing Machine mode. Is it more power than the basic turing machine? Justify your answer. 
6 Using Pumping lemma Show that the language L={ an bn cn |n>=1} is not a CFL. 
7 What is meant by a Turing Machine with two way infinite tape. 
8 Define instantaneous description of a Turing Machine. 
9 What is the class of language for which the TM has both accepting and rejecting configuration? Can this be called a Context free Language? 

10.The binary equivalent of a positive integer is stored in a tape. Write the necessary transition to multiply that integer by 2. 
1 What is the role of checking off symbols in a Turing Machine? 
2 State Pumping lemma for Context free language. 
3 Define a Turing Machine. 
4 Mention any two problems which can only be solved by TM. 
5 State Pumping lemma and its advantages. 
6 What are useless symbols in a grammar. 

PART-B 
1.a)Find a grammar in Chomsky Normal form equivalent to S->aAD;A->aB/bAB; B->b, D->d. (6)
b)Convert to Greibach Normal Form the grammar G=({A1, A2, A3},{a,b},P,A1 ) where P consists of the following. A1 ->A2 A3, A2 ->A3 A1 /b,A3 ->A1 A2 /a. (10) 
2.a)Show that the language {0n1n22/n>=1} is not a Context free language. (6) 
b)Convert the grammar S->AB, A->BS/b, B->SA/a into Greibach NormalForm. (10)
3.a)Construct a equivalent grammar G in CNF for the grammar G1 where G1 =({S,A,B},{a,b},{S->bA/aB,A->bAA/aS/a, B->aBB/bS/b},S) (12) 
b)Obtain the Chomsky Normal Form equivalent to the grammarS->bA/aB, A->bAA/aS/a, B->aBB/bS/b. (4)
4.a)Begin with the grammar 
S->0A0/1B1/BBA->CB->S/AC->S/ ε
and simplify using the safe order Eliminate ε-Productions Eliminate unit production Eliminate useless symbols Put the (resultant) grammar in Chomsky Normal Form (10) 
b)Let G=(V,T,P,S) be a CFG. Show that if S=α, then there is a derivation tree in a grammar G with yield α. (6) 
5.a)Let G be the grammar S->aS/aSbS/ ε. Prove that L(G)={x/each prefix of x has atleast as many a's as b's} (6) 
b)Explain the Construction of an equivalent grammar in CNF for thegrammar G=({S,A,B}{a,b},P,S)
where P={S->bA|aB, A->bAA|aS|a, B->aBB|bS|b} (10) 
6.a)Find a Context free grammar with no useless symbol equivalent to 
S->AB/CA, B->BC/ABA->a, C->aB/b. (6)
b)Show that any CFL without εcan be generated by an equivalent grammar in Chomsky Normal Form. (10) 
7.a)Convert the following CFG to CNF S->ASA|aB A->B|S B->b| ε(12) 
b)Explain about Greibach Normal Form. (4) 
8.a)Is L={an bn cn /n>=1} a context free language? Justify Your answer. (8) 
b)Prove that for every context free language L without εthere exists an equivalent grammar in Greibach Normal Form. (8) 
9.State and Prove pumping lemma for Context free languages. (16) 
10.a)State Pumping Lemma for context free language. Show that (0n 1n 2n/n>=1} is not a Context free language. (6) 
b)State Pumping lemma for context free language σshow that language {ai bj ci dj/i>=1, and j>=1} is not context-free. (6) 
11.a)Design a Turing Machine M to implement the function “multiplication” using the subroutine ‘copy’. (12) 
b)Explain how a Turing Machine with the multiple tracks of the tape can be used to determine the given number is prime or not. (4) 
12.a)Design a Turing Machine to compute f(m+n)=m+n, V m,n>=0 and simulate their action on the input 0100. (10) 
b)Describe the following Turing machine and their working. Are they more 
powerful than the Basic Turing Machine? Multi-tape Turing Machine Multi-Dimensional Turing Machine 
(3) Non-Deterministic Turing Machine. (6) 
13.a) Define Turing machine for computing f(m,n)=m-n ( proper subtraction). 
(10) 
b)Explain how the multiple tracks in a Turing Machine can be used for testing given positive integer is a prime or not. (6) 
14.a)Explain in detail:” The Turing Machine as a Computer of integer functions”. (8) 
b)Design a Turing Machine to accept the language L={0n 1n/n>=1} (8) 
15.a)What is the role of checking off symbols in a Turing Machine? (4) 
b)Construct a Turing Machine that recognizes the language
{wcw/w in {a+b}+ } (12) 

16.Prove that the language L is recognized by a Turing Machine with a two way infinite tape if and only if it is recognized by a Turing Machine with a one way infinite tape. (16) 
17.For each of the following Context free languages L, find the smallest pumping length that will satisfy the statement of the Context free pumping lemma. In each case, Your answer should include a number(the minimum pumping length), a detailed explanation of why that the number is indeed a valid pumping length for the given language L, and a detailed explanation of why no smaller number qualifies as a valid pumping length for that particular language L. 
  (i) L={an bn|n>=0} (6) 
  (ii) L={w in {a,b}*|w has the same number of a’s and b’s} (6) (iii)L={w in {a,b}*| w has twice as many a’s as b’s.} (4) 

18.Design a Turing Machine M that decides A={0k /n>0 and k=2n } the language consisting of all strings of 0’s whose length is a power of 2. (16) 
19.a)Give a High level implementation description with a neat sketch of a Turing Machine M that performs the following computation.M=on input w: writes a copy of w on the tape immediately after w,leaving the string w#w on the tape.Assume that the input string initially appears at the left most end of the tape and that the input alphabet does not contain the blank character’ : The end of the input string is therefore determined by the location of the first blank cell on the input tape. The symbol # is assumed to be in the tape alphabet,and the input alphabet is {a,b}. 
(12) 
b)Demonstrate the working of your TM with an example. (4) 
20.a)Show that the language{0n 1n 2n/n>=1}is not context free. 
(8) 
b)Show that the context free languages are closed under union operation but not under intersection. (8) 
UNIT-V UNDECIDABILITY 
PART-A 
1 When a recursively enumerable language is said to be recursive. 
2 Is it true that the language accepted by a non deterministic Turing Machine is different from recursively enumerable language? 
3 When we say a problem is decidable? Give an example of undecidable problem? 
4 Give two properties of recursively enumerable sets which are undecidable. 
5 Is it true that complement of a recursive language is recursive? Justify your answer. 
6 When a language is said to be recursive or recursively enumerable? 
7 When a language is said to be recursive? Is it true that every regular set is not recursive? 
8 When a problem is said to be decidable or undecidable? Give an example of an undecidable. 
9 What do you mean by universal Turing Machine? 

10.When a problem is said to be undecidable? Give an example of an decidable problem. 
11.Show that the union of recursive language is recursive. 
12.Show that the union of two recursively enumerable languages is recursively enumerable. 
13.What is undecidability problem? 
14.Show that the following problem is undecidable.“Given two CFG’s G1 and G2, is L(G1)∩L(G2)=Φ?”. 
15.Define Ld. 
16.Define recursively enumerable language. 
17.Give an example for a non recursively enumerable language. 
1 Differentiate between recursive and recursively enumerable languages. 
2 Mention any two undecidability properties for recursively enumerable language. 

21.Define Diagonal languages. 
22.Give an example for an undecidable problem. 
PART-B 
1.a)Show that union of recursive languages is recursive. 
(4) 
b)Define the language Ld and show that Ld is not recursively enumerable language. (8) 
c)Explain the Halting problem. Is it decidable or undecidable problem 
(4) 
2.Define Universal language Lu.Show that Lu is recursively enumerable but 
not recursive.  
3.a)Obtain the code for the TM M=({q1,q2,q3},{0,1},{0,1,B}, δ,q1,B,{q2}) With the moves δ(q1,1)=(q3,0,R) δ(q3,0)=(q1,1,R) δ(q3,1)=(q2,0,R) δ(q3,B)=(q3,1,L) δ(q3,B)=(q3,1,L)  
b)Show that Ln is recursively enumerable.  

4.a)Define Ld and show that Ld is not recursively enumerable. 
(12) 
b)Whether the problem of determining given recursively enumerable language is empty or not? Is decidable? Justify your answer. 
(4) 5.Define the language Lu. Check whether Lu is recursively enumerable? or Lu is recursive? Justify your answer. (16) 6.a)Show that the language Ld is neither recursive nor recursively enumerable. (12) b)Describe how a Turing Machine can be encoded with 0 and 1 and give an example. (4) 7.a)Show that any non trivial property J of the recursively enumerable 
languages is undecidable. (8) b)Show that if L and L are recursively enumerable then L and L recursive. 
 8.Define the universal language and show that it is recursively enumerable 

but not recursive. (16) 
9.Prove that the universal language Lu is recursively enumerable. (16) 
10.State and Prove Rice’s Theorem for recursive index sets. (16) 

11.a)Show that the following language is not decidable. L={<M>| M is a TM that accepts the string aaab}. (8) 
b)Discuss the properties of Recursive and Recursive enumerable languages. (8) 
12.a)Define Post correspondence problem with an example. (8) 
b)Prove that the function f(n)=2n does not grow at a polynomial rate, in other words, it does not satisfy f(n)=O(np ) for any finite exponent p. 
13.a)Define the language Ld.Show that Ld is neither recursive nor recursively enumerable. (12) 
b)Show that if a language L and its complement L are both recursively enumerable then L is recursive. (4) 14.a)What are the features of a Universal Turing Machine? (4) 
b)Show that “If a language L and its compliment L are both recursively enumerable,then both languages are recursive”. (6) 
c)Show that halting problem of Turing Machine is undecidable. (6) 
15.a)Does PCP with two lists x=(b,b ab3,ba) and y=(b3 ,ba , a)have a solution?. (6) b)Show that the characteristic function of the set of all even numbers is recursive. (6) c)Let ∑={0,1}.Let A and B be the lists of three strings each,defined as List A List B 
i Wi Xi1 1 1112 10111 10310 0
Does this PCP have a solution? (4) 
16.a)Show that it is undecidable for arbitrary CFG’s G1 and G2 whether L(G1)∩L(G2)Is a CFL. (8) 
b)Show that “finding whether the given CFG is ambiguous or not” is undecidable by reduction technique. (8) 
17.Find whether the following languages are recursive or recursively enumerable. 
(i) Union of two recursive languages. (4) 
(ii) Union of two recursively enumerable languages. (4) 

(iii) L if L and complement of L are recursively enumerable. (4)(iv)Lu (4)
18. Consider the Turing Machine M and w=01, where M=({q1,q2,q3},{0,1},{0,1,B},δ,q1,B,{q3}) and δis given by 
Reduce the above problem to Post’s correspondence Problem and find whether that PCP has a solution or not. (16) 
2 Explain the Post’s Correspondence Problem with an example (16) 

3 Find the languages obtained from the following operations: 

qi δ(qi, 0) δ(qi, 1) δ(qi, B) 
Q1 (q2,1,R) (q2, 0,L) (q2, 1,L) 
q2 (q3, 0,L) (q1, 0,R) (q2, 0,R) 
q3

(i) Union of two recursive languages. (6) 
(ii) Union of two recursively enumerable languages (6) 
(iii) L if L and complement of L are recursively enumerable (4) 

read more