COCS5315
Final Exam.
2008, Special Edition
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. l:
The Empty-symbol
Name (PRINT)_______________________________________
PART-A.
Multiple Choice questions
(80 points)
Choose and answer 20 questions in this PART-A.
For each question in this PART-A, write down a big A,B,C,D,E, or F (in
capital) precisely next to
each question number and nowhere
else.
The first six 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
1.
The language accepted by this TM is:
a.
a
a*
b*
a*
b.
a
a*
b* a a*
c.
neither.
2.
The function computed by this TM is
a.
partially computable
b.
Computable
c.
both.
d.
neither.
3.`
The function computed by this TM is
a.
strictly computed.
b.
non-strictly computed.
c.
primitive recursive
d.
two above.
e.
none above.
4.
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
5.
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.
6. 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 six questions are about the following CFG (Context-Free Grammar):
S -> P a Q
S -> a P
R -> a T
T -> P Q
P -> Q S Q
P -> Q
Q -> l
Q -> b Q
10. Which non-terminal is Nullable?
a. Q and P
b. T and S c. both. d. neither.
11. Which is an implicit (implied) Unit-Production Rule?
a. T -> Q
b. T -> P
c. S -> P d. all. e. two. f. none.
12. Which production rule is to be added to this grammar as a result of eliminating empty-
production-rule?
a. S -> a Q
b. S -> P a
c. Q -> b d. all above. e. two. f. none above.
13. 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. S -> P a P
c. S -> a Q
d. All above. e. two above. f. none above.
14.
Which production rule satisfies the CNF but not the
GNF?
a.
T -> TP
and T ->
PQ
b.
R -> aT
and Q -> bQ
c.
Both.
d.
neither.
15.
The index of
RL on the
language defined by this grammar is
a.
infinite
b.
no greater than the number of
non-terminals of the grammar.
c.
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 NPDA’s and all
DCFL’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 grammar defines a non-empty
language.
d.
All.
e.
Two.
f.
None.
19.
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.
20.
Which WFF’s are equivalent?
a.
%X%Y(P(X)+Q(Y))
b.
%X(P(X)) + %Y(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))
24.
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.
25.
The Resolution Principle is to
establish
a.
the validity of negated
WFF’s
b.
the contradiction of negated
WFF’s
c.
neither.
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
a.
a DPDA by the final
state(s).
b.
a DPDA by the
empty-stack.
c.
an NPDA by the
empty-stack.
d.
All above
e. two above.
f. none
28.
The index of RL defined on this language
is
a.
finite but greater than the
number of non-terminals of a grammar that defines the
language.
b.
infinite as the language is not
regular.
c.
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 ba* b (b* + aa* b)*
b.
a* ba* 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.
CFL’s
d.
All bove.
e. two above.
f. none
above.
33.
Some
students are honest and study-hard.
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?
a.
P(X, f(X)) and P(g(Y), Y)
b.
P(X, f(X)) and P(g(Y), Z)
c.
both.
d. neither.
PART-B.
Other problems
(80 points)
Do six 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 }
G.
Show a PDA that accepts L = {wcwR | w is in (a,b)* }
H.
Convert
the following to a CNF form and clearly show the results:
S ->
a S b
S ->
R
R -> ( S
)
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 at least three
operations under which CSL’s are closed.