CS701 - Mid Term Papers
Question 1
Objective Questions [of 10 Marks (I think)]
Question 2
A TM was given and we were to write sequence of
configurations for it
Question 3
PCP match question having two parts.
Considering the given instances of Post Correspondence Problem (PCP)
we were to tell if it was possible to find a match for every PCP instance. If
YES, then we were to give the dominos arrangement which will result in a match.
If NO, then prove
Question 4
One question was related to writing implementation description of TM
Question 5
One question was to describe string (0,1)* using
diagnolization is countable or not
Q.1 EMPTINESS problem for LBA is decidable ?
1. TRUE
2. FALSE
Q.2 A property that holds for almost all
strings also hold incompressible strings ?
1. TRUE
2. FALSE
Q3. For a TM M and string w
={x|x is an acceptable computation History M on w}.
Then
is decidable ?
1. TRUE
2. FALSE
Q.4 A string x is b-compressible if
K(x)>|x|- b ?
1. TRUE
2. FALSE
Q5. If L is decidable Language
will also be decidable ? Note(
demotes reverse
of Language)
1. TRUE
2. FALSE
Q.6 A correspondence or one-to-one
correspondence is a function that both one-to-one and onto ?
1. TRUE
2. FALSE
Q.7 Time
contains Time (n log n tha ya n
)
1. TRUE
2. FALSE
Q.8 If A reduces to B, It is not necessary that
compliment of A reduces to compliment of B ?
Q.9
yields
?
1.
=
Correct Option
rest of three are not in mind.
Q.10 Let
Which String
belongs to L?
1. aabb
2. aabbcccc
3. aaabbccc
4. aabbbccc
Q.11 Consider following instance of Post Correspondence
Problem (PCP). Is it possible to find a match for PCP instance given below? If
YES, then give the dominos arrangement which will result in a match. If NO, then
prove. 05 Marks
Q.12 Consider the sentence,
10
Marks
Let
assign "PLUS" TO R, where "PLUS" (a,b,c) is True whenever
a+b=c, If "Universe" is R(Real Number). Is this sentence True ?
Justify your answer?
Q.13 Consider the pair of numbers 234 and 399.
show that they are relatively prime or not ? 10
Marks
Q.14 Prove
PCP decidable for unary alphabet
10 Marks
Q.15 Prove
that
? 10
Marks
Q.17
Show that Show that the collection of decidable
languages is closed under the operation of concatenation. 10
Marks
Q.16 Let t(n) be a function, where
. Then every t(n) time
nondeterministic single tape TM has an equivalent
time
deterministic single tape TM. 10 Marks
Q1: let x be the set {1,2,3,4,5} and y be the set
{6,7,8,9,10}we describe the functions f:xày
and g:xày
in the following table
n
|
F(n)
|
n
|
G(n)
|
|
1
|
6
|
1
|
10
|
|
2
|
7
|
2
|
9
|
|
3
|
6
|
3
|
8
|
|
4
|
7
|
4
|
7
|
|
5
|
6
|
5
|
6
|
Is f onto?justify
Q2:consider the pair of numbers 1274 and 10505 show that
they are relatively prime or not?
Q3.let L={<M>!M is a tm and if we start m with a blank
input tape then it will finally writes some non blank symbol on its tape} is L
decidable?
Q4let LAll={<M>!M is a tm with input
alphabet sigma and L(M) = sigma* }prove that LAllis not turing recognizeable.
Q5show that
if A is turing reducible to be ,b is turing reducible to c, c is turing
reducible to A.
Q6.A useless
state in a turing machine is one that is never entered on any input string
consider the problem of determining whether a turing machine has any useless
states and formulate this problem as a language and show that it is
undecidable.
Q7.Let t(n)
be a function where t(n)≥n show that every t(n) time k-tape TM has an
equivalent O(t2(n)) time single type M.