COCS5315
Final Exam.
5/5/2008
Name: (Print in
CAPITAL or else you love FIVE points)
______________________________________________________
In
this test, the following notations are used:
1. $:
Universal Quantifier.
2. %:
Existential quantifier.
3. ^:
Conjunction operator. (AND)
4. +:
Disjunction operator. (OR)
5. ~:
Negation operator. (NOT)
6. ->:
Implication operator (IMPLIES)
7. V,W,X,Y,Z: A
variable.
8. a,b,c,d:
A constant.
9. f,g,h:
A function.
10. P,Q,R,S: A predicate
Symbol.
11. RM
The
right-invariant equivalence relation defined on a DFSA, M
12.
RL
The right-invariant equivalence relation defined on a language, L
13. CFG(L)
Context-Free Grammar (Language)
14. RE :
Recursively Enumerable
15. DCFL:
Deterministic CFL
14. WFF:
Well-formed formula (in any logic system)
16. l:
The Empty-symbol
17. PC:
Partially Computable.
18. PR:
Primitive Recursive
PART-A. Multiple Choices.
(102 points)
For each question in this PART-A, make exactly one choice by clearly writing down A,B,C,D,E, or F (in capital)
next to each question number and
nowhere else. (If not followed, you lose FIVE
points)
First three questions are about the following set:
S = {x | g(r(<l(x), r(x)>)) is defined where g(x) is a PC function of one argument}
1. The problem of deciding whether or not the set S is Recursive is the same as deciding whether or not
a. ~S is Recursive
b. S is RE c. both. d. neither.
2. The problem of deciding whether or not g(x) is the same as g(r(x)) is the same as deciding whether or not
a. <l(x), r(x)> is the same as x
b. r(x) is the same as x
c. both. d. neither.
3. The problem of deciding whether or not the set K is many-one reducible to this set S is
the same as deciding whether or not
a. ~S is m-Complete.
b. S appears infinitely many times in the “Enumeration of All RE sets.”
c. Both. d. neither.
The
next five questions are about the following quadruple TM of twelve
quadruples.
Note that this TM, M, has 5 states, q1, q2, q3, q4 and q5, on
the alphabet, {a,b}
and the only accepting
combination is (q5, B).
N1:
q1
B
R
q2
N2:
q2
a
R
q3
N3:
q2
b
b
q2
N4:
q2
B
B
q2
N5:
q3
b
R
q4
N6:
q3
a
a
q3
N7:
q3
B
B
q3
N8:
q4
b
R
q4
N9:
q4
a
R
q5
N10:
q4
B
B
q4
N11:
q5
a
R
q5
N12:
q5
b
b
q5
4.
The language accepted by this TM is:
a.
a
a*
b*
a*
b.
a
a*
b* a a*
c.
neither.
5.
The function computed by this TM is
a.
partially computable
b.
Computable
c.
strictly computed
d.
all above.
e. two above.
6.
In which case, this TM will not stop?
a.
q2
B
b.
q5
B
c.
q3
a
d.
all above.
f.
two above
Q5
B
B
Q5
7.
Suppose that above quadruple replaced the quadruple N12 above. In this
case, this TM would
a.
compute the same function as before.
b.
accepts the same language as before
c.
both.
d.
neither.
8. Which string is accepted by this TM?
a. a a a a
b. a b a a a
c. a b b
d. all above. e. two. f. none.
Next seven questions are about the following CFG (Context-Free Grammar):
S -> P a Q b
S -> P S Q
S -> a P T
S -> P
T -> T Q
P -> P T
P -> Q Q
Q -> l
Q -> b Q
9. Which is useless?
a. T
b. P and Q
c. both. d. neither.
10. Which rule is to be eliminated as a result of eliminating useless symbol or symbols?
a. S -> a P T
b. P -> P T
c. T -> T Q
d. all above. e. two above. f. none above.
11. Which non-terminal is Nullable?
a. Q and P
b. S
c. both. d. neither.
12. Which is an implicit (implied) Unit-Production Rule?
a. P -> Q
b. S -> Q
c. S -> P
d. all. e. two. f. none.
13. Which production rule is to be added to this grammar as a result of eliminating empty production-rule?
a. S -> S Q
b. S -> P a b
c. Q -> b
d. all above. e. two. f. none above.
14. Which production rule is to be added to this grammar as a result of eliminating Unit production rule(s)?
a. S -> Q a Q b
b S -> P a P b
c. S -> Q
d. All above. e. two above. f. none above.
15.
Which production rule satisfies the CNF but not the
GNF?
a.
T -> T P
b.
Q -> b Q
c.
Both.
d.
neither.
16.
Which pair is equivalent?
a. All
DFSA’s and all Regular grammars.
b. All
TM’s without any accepting state and all TM’s with one or more accepting
states.
c.
All LBA’s and all
CSL’s
d.
all.
e. two.
f.
none.
17.
Which is solvable?
a.
deciding whether or not the index of RL defined on a CFL is
finite.
b.
deciding whether or not an arbitrary grammar defines a type-0
language.
c.
deciding whether or not an arbitrary CFG defines a non-empty
language.
d.
All.
e.
Two.
f.
None.
18.
Which WFF’s are equivalent?
a.
$X$Y(P(X)^Q(Y))
b.
$X(P(X))^$Y(Q(Y))
c.
$Y$X(P(X)^Q(Y))
d.
all above.
e.
two above.
f.
none above.
19.
Which is solvable?
a.
deciding whether or not the complement of an arbitrary CFL is
CF
b.
deciding whether or not the complement of an arbitrary DCFL is
DCF
c.
deciding whether not the intersection of an arbitrary CFL and an
arbitrary Regular language is CF.
d.
all above.
e.
two above.
f.
none above
20.
Which WFF’s are equivalent?
a.
%X%Y(P(X)+Q(Y))
b.
%X(P(X) + Q(Y))
c.
%Y%X(Q(X)+P(Y))
d.
all above.
e.
two above.
f.
none above.
21.
Which WFF is valid?
a. $X$Y$Z ((P(X) -> Q(Y))^(Q(Y)->R(Z)) ->
(P(X)->R(Z)))
b.
$X%Y (P(X,Y)) -> %X$Y (P(X,Y))
c.
%X$Y (P(X,Y)) -> $Y%X (P(X,Y))
d.
all above.
e.
two above.
f.
none above.
$X$Z%Y ((P(X)+Q(Z)+~S(Y)) ->
R(Y))
22.
Which clause is included in the above WFF ?
a.
~P(X)+R(f(X,Z))
b.
~Q(Z)+R(f(X,Z))
c.
~P(X)^~Q(Z)^S(Y) + R(Y)
d.
all.
e. two.
f.
none.
23. The
Resolution Principle is to establish
a.
the validity of negated WFF’s
b.
the contradiction of negated WFF’s
c.
Both.
d.
neither.
24.
Which strategy is complete?
a.
Input Strategy and Unit Strategy
b.
AF Form Strategy
c.
Set of Support Strategy as the Set of Support should contain clauses
without which other remaining
input clauses together will be satisfiable.
d.
all above.
e.
two above.
f.
none above
25.
Which is contained in the NP Class of problems (or
languages)
a.
all problems in the P Class
b.
problems that are non-deterministically polynomially
solvable.
c.
problems that are exponentially solvable.
d.
all above.
e.
two above.
f.
none above.
The next three questions are
about the following language:
{ am bm cm |
m>=1 }
26. This
language is
a.
CF
b.
DCF
c.
Regular
d. two above.
e. none above
27. This
language can be accepted by
d.
a DPDA by the final
state(s).
e.
a DPDA by the
empty-stack.
f.
an NPDA by the
empty-stack.
g.
All above
e. two above.
f. none
28.
The index of
RL defined on
this language is
h.
finite but greater than the
number of non-terminals of a grammar that defines the
language.
i.
infinite as the language is not
regular.
j.
neither.
The next three questions are
about the following DFSA with five states:
(1, a, 1)
(1, b, 2)
(2, a, 3)
(2, b, 4)
(3, a, 2)
(3, b, 4)
(4, a, 5)
(4, b, 4)
(5, a, 5)
(5, b, 4) where each triple is (originating-state,
input-symbol, terminating-state)
and two states state-4 and
state-5 are accepting.
29.
There is no “Distinguishing” string (which can be the empty-string)
between
a.
state-1 and state-2
b.
state-2 and state-3
c.
state-4 and state-5
d.
all above.
e. two above.
f. none above.
30. Which
pair of two strings is equivalent with respect to RM ?
a.
“aab” and
“ab”
b.
“aa” and “abaa”
c.
both.
d.
neither.
31. This
DFSA accepts
a.
a b a* b (b* + aa* b)*
b.
a* b a*
b (b*
+ aa* b)*
c.
a* b a*
b b*
d.
none above.
32. Which
is closed under both Intersection and Complementation?
a.
Type-3 (regular)
languages.
b.
DCFL’s
c.
CSL’s
d.
All bove.
e. two above.
f. none
above.
Some students are honest and study-hard.
33.
Which most adequately describes the above
assertion?
a.
$X (student(X) ->
honest(X)^hard(X))
b.
%X (student(X) -> honest(X)^hard(X))
c.
$X (student(X) ^ honest(X) ^
hard(X))
d.
%X (student(X) ^
honest(X) ^ hard(X))
34.
Which two predicates can be unifiable?
e.
P(X, f(X)) and P(g(Y), Y)
f.
P(X, f(X)) and P(g(Y), Z)
g.
both.
d. neither.
PART-B.
Other problems
(58 points)
Do
five problems.
A.
{ am bn cn |
m,n >= 1 }
Give a sufficiently long string of the above language and show a possible
decomposition of
this string that satisfies the CFL Pumping Lemma or the Regular Language
Pumping Lemma.
B.
Give all clauses for:
%X$Y%Z ((P(X)+R(Z)) -> (S(Y)+Q(Z)))
C.
Prove each is a
CFL.
a.
{ am bm cn | m,n >=1 }
b.
{ am bn cm | m,n >=1 }
c.
{ am bm cn dn | m,n >=1 }
D.
Give two DCFL’s whose union is
not a DCFL.
E.
Show that not every Recursive
language is CS.
F.
Show a grammar (possibly CS) that
defines
L = { am bm
cm | m >= 1 }
C.
Show a PDA that accepts L = {wcwR | w is in (a,b)* }
D.
Convert
the following CFG to an equivalent CNF form and clearly show the
results:
S ->
a S b
S ->
R
R -> R Q
R -> ( Q
)
Q -> c Q
Q ->
l
I.
Give a CFL that is not a DCFL.
And, show that it is, in fact, not a DCFL.
J.
Reduce the following PCP system to CFG ambiguity
problem.
ab
ba
aba
bab
aa
bbb
bb
aaa
K.
List at least three operations under which CFL’s are
closed.
And, also list at least three
operations under which CSL’s are closed.