Keys:
1-5:
DDBBE
6-10:
DDAAD
11-15: ABBCD
16-20: AADDD
21-25: CDDD(C)A
COSC3302
TEST-2
4/28/2005
NAME__________________________________________________
THROUGHOUT THIS TEST,
THE FOLLOWING NOTATIONS ARE APPLICABLE:
1. RE: Recursively
Enumerable
2. PC: Partially
Computable
3. TM: Quadruple Turing Machine.
(deterministic with 2-way infinite
tape)
4. NDTM:
Nondeterministic quadruple TM
5. S.L. The Simple Language with the
following three BASIC instructions:
V = V+1
V = V-1
IF V <> 0 GOTO L
6. NPDA Nondeterministic pushdown
automata.
PART-A.
Multiple Choice Questions.
(75 points)
1.
Which is a Macro that can be
implemented solely by the three instructions in S.L.?
a.
GOTO L
b.
V = 0
and V =
W
c.
V = V1 + V2 and V = V1 *
V2
d.
All.
e. two.
f.
none.
2.
Which is
Solvable?
a.
TM Halting
Problem
b.
TM State
Problem.
c.
Both.
d. Neither
3.
Which is
Solvable?
a.
Membership Problem for RE
sets.
b.
Membership Problem for Recursive
sets.
c.
Both.
d. neither.
4.
Which is
Computable?
a.
Halt(x,x)
b.
STP(x,y,t)
c.
Both.
d. neither.
5.
Which preserves Computable
functions?
a.
composition
b.
primitive
recursion
c.
unbounded minimalization
d.
all.
e. two
f. none
6.
Which preserves PC
Functions?
a.
composition
b.
primitive
recursion
c.
unbounded minimalization
d.
all.
e. two
f. none
7.
All TM’s are equivalent
to
a.
all RE sets.
b.
All SL
programs.
c.
All PC
functions.
d.
All.
e. two.
f. none.
8.
RE sets are closed
under
a.
b.
Complementation.
c.
Both.
d. neither.
9.
All CFL’s are equivalent
to
a.
all NPDA.
b.
All TM’s
c.
All RE sets.
d.
All of above.
e. two.
f. none
10. Suppose that a family of languages
is closed under union and also under intersection. In this
case,
a.
it is closed under
complementation.
b.
Any proper subset of this family is
closed under union.
c.
Both.
d. neither
11. Suppose that a family of languages
is NOT closed under union and NOT closed under intersection. In this
case,
a.
it may or may not be closed under
complementation.
b.
Any proper subset of this family is
not closed under union.
c.
Both.
d. neither.
12. Suppose that Problem A is reduced
to Problem B. In this case,
a.
Problem A is at least as hard as
Problem B.
b.
Problem B is at least as hard as
Problem A.
c.
Both.
d. neither.
13. <3, <2,4>> is
a.
568
b.
567
c.
neither.
14. All deterministic quadruple TM’s
with 2-way infinite tape are equivalent to
a.
all deterministic quintuple TM’s with
2-way infinite tape.
b.
all non-deterministic quintuple TM’s
with 1-way infinite tape.
c.
Both.
d.
neither.
Next three questions are about a TM with
the following seven quadruples:
Q1 B R Q2
//Quad-1
Q2 1 R Q3
//Quad-2
Q3 1 R
Q4
Q4 B B
Q5
Q2 B B
Q5
Q4 1 R Q3
//Quad-6
Q3 B B Q3 //Quad-7
15. Which string is accepted by this
TM?
a.
11
b.
1111
c.
111111
d. all.
e.
two.
f. none
16. The language accepted by this TM
is
a.
{l , 11, 1111, 111111, 11111111, … ,
infinity}
b.
{11, 1111, 111111, 11111111, … ,
infinity}
c.
{l , 111, 111111, 111111111, 111111111111, …
, infinity}
d.
none above.
17. The purpose of quadruple-7 above
is
a.
to not accept the current input
string.
b.
to enter an infinite loop thereby
accepting the input string.
c.
Both.
d.
neither.
18. Which is
Computable?
a. f(X1,X2) = X1+X2 and f(X1,X2) =
X1*X2
b.
f(X1,X2) = integer(X1/X2)
c.
f(X1,X2) =
integer(Remainder(X1/X2))
d.
all.
e. two.
f.
none
19. Which is
Computable?
a.
P(X1,X2) = whether or not X1 and X2
are the same
b.
P(X1,X2) = whether or not X1 is a
divisor of X2
(like 4 and 8 but not 4 and 9 nor 4 and
10)
c. P(X1,X2) =
whether their difference is zero or not.
d.
all.
e. two.
f. none.
20.
Which is CF???
a. L1 = {bm cn |m,n>=0}
b. L2 = {am
bn cn dm |m,n>=0}
c.
L3 = {am bm cn dn |m,n>=0}
d.
All.
e. two.
f. none
21. Any CFL without the empty string in it
can be represented by
a.
CNF
b.
GNF
c.
Both.
d.
neither.
Next four questions are about the
following CFG:
S ->
S R S
S -> R
R -> P Q
Q -> (
)
Q -> (
S )
Q ->
P
P -> R
// rule-7
P -> l
22. Which string is in the language generated
by this CFG?
a.
l
b.
( ( ) ) ( ( )
)
c.
( ( ) ) ( ( ) ) (
)
d.
All.
e. two.
f. none.
23.
Which non-terminal is Nullable?
a.
P
b.
Q
c.
R
d.
All.
e. two.
f. none.
24. If rule-7 is eliminated, the resulting
equivalent grammar will be
a.
S -> S R
S
S -> S S
S -> R
R -> P
Q
R ->
P
Q -> ( )
Q -> (
S )
P -> l
b.
S -> S R
S
S -> S S
S -> R
R -> P
Q
R ->
Q
R ->
P
Q -> (
)
Q -> (
S )
P -> l
c. both.
d.
neither.
25. Suppose that the following string
is sufficiently long:
(())(())(())
In this case, which decomposition
of this string into five parts will satisfy the CFL Pumping
lemma?
a. u = “(())”
b. u = l
v = “(“
v =
“(“
w = ”()”
w =
“()”
x = “)”
x =
“)((“
y = “(())”
y = “))(())”
c. both.
d.
neither.
PART-B. Other problems.
(25
points)
Do three
problems in this PART.
A. L1 = {am bm cm |m
>= 0}
L2 = {am bn cm
|m,n>=1}
Prove or disprove that each language above is CF.
B. Give a program which the
Predicate HALT(X,X) would
contradict.
And, then describe some key points for that.
C. Give an example language
which no deterministic push-down automaton can
accept.
And, then give reasons why that is
the case.
D. Design a TM that accepts L =
{111, 111111, 111111111,…, infinity}
E. List various types of
languages along with their characteristics and
corresponding accepting
devices.
And, indicate cases where determinism and non-determinism do not
coincide and brief reasons of why they do
not.
F. Define the Macro: X=V
in terms of the
following:
V = V+1
V = V-1
If (V <> 0) goto L
Goto L
V = 0
Note that the current value of the righthand
side variable, V,
should not be changed at the end of the
instruction.