SRM University 2007 B.Tech Computer Science and Engineering BANK : THEORY OF COMPUTATION - Question Paper
Wednesday, 30 January 2013 10:15Web
Page 2 of 3
5)Give an eample of a language accepted by a PDA but not by DPDA.
6)Describe the 2 kinds of moves of PDA.
7)Describe the instantaneous Description of a PDA.
8)When is a PDA stated to be deterministic?Are the deterministic and non-deterministic models of PDA equivalent with respect to the language accepted?
9)State the pumping lemma for CFL.
10)What is the use of pumping lemma for CFL?(Applicatons.)
UNIT- IV
1)Define Turing machine.
2)Define ID and Move of a Turing machine.
3)Define the language accepted by a TM.
4)Is it possible that a TM could be considered as computer of functions from integers to integer?If yes,justify your ans.
5)Define total recursive and partial recursive functions.
6)When a language is stated to be recursively enumerable?
7)When is the technique of checking of symbols useful?
8)Define Multiple Turing machine.
9)When is the technique of shifting over useful?
10)List a few of the replaced versions of of the basic model of a TM.
11)Define Multidimensional TM.
12)Define Multihead TM.
13)What is an off-line TM.
14)When is a function ‘f’ stated to be “Turing computable”?
15)Construct a TM to calculate the function f(x)=x+2.
16)Construct a TM that accepts strings over{1} containing even number of 1’s.
17)Explain how a TM with multiple tracks of the tape can be used to determine the provided number is prime or not?
UNIT V
1) When a issue is stated to be decidable and provide an example of an undecidable problem?
2) What is undecidability?
3) discuss the replaced Part’s Correspondance Problem(MPCP).
4) Differentiate recursive and recursively enumerable language.
5) provide the properties of recursively enumerable sets which are undecidable.
6)Show that the union of recursive languages is recursive.
7)Explain the Halting issue.Is it decicable or undecidable problem?
8)Define universal language Lu.
9)Obtain the code for
M=({q1,q2,q3},{0,1},{0,1,B},d,q1,B,{q2}) have moves;
10)Define the language Ld.
PART-B
UNIT -I
1) If L is a set accepted by an NDFA, then show that L is accepted by a DFA.
2) If L is a set accepted by an NDFA with e - transition ,then show that L is accepted by an NDFA without e- transition.
3) Let ‘r; be a regular expression . Then ,show that there exists an NDFA with e- transitions that accepts L(r).
| Earning: Approval pending. |
