COSC5315
Test-2
4/23/2008
Name
(Please PRINT, else you lose 5
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. RE :
Recursively Enumerable
12. CFG(L)
Context-Free Grammar (Language)
13. DCFL:
Deterministic CFL
14. WFF:
Well-formed formula (in any logic system)
15. l:
The Empty-symbol
PART-A. Multiple Choices.
(72 points)
For each question in this PART-A, make exactly one choice by clearly writing down A,B,C,D,E,F or G(in capital) next to each question number and nowhere else.
First five questions are about the following CFG (Context-Free Grammar):
S -> P a P
S -> P Q
S -> a T
P -> Q Q
P -> S
T -> T Q
Q -> Q T
Q -> l
Q -> b Q
1. Which is a useless grammar symbol?
a. P
b. T c. both. d. neither
2. Which non-terminal is Nullable?
a. P
b. Q and S c. both. d. neither.
3. Which production rule is to be added to this grammar as a result of eliminating empty-production-rule(s)?
a. S -> P a
b. S -> a
c. Q -> b d. all above. e. two. f. none above.
4. Which production rule is to be added to this grammar as a result of eliminating Unit production rule(s)?
a. S -> S a S
b. S -> S a P c. both. d. neither.
5.
Which production rule is to be eliminated due to the elimination of
useless symbol(s)?
a.
T -> T
Q
b.
Q -> Q T
c.
S -> a T
d.
All above
e.
two above.
f.
none above.
6.
Which pair is equivalent?
a. All
DFSA’s and all Regular grammars.
b.
All NPDA’s and all
CFL’s
c. both.
d.
neither.
7.
Which pair is equivalent?
a.
All DFSA’s and all NFSA’s
b.
All NPDA’s by accepting states and all by the empty
stack.
c.
All NPDA’s and all DPDA’s
d.
all above.
e.
two above.
f. none
above
8.
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.
9.
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.
10.
Which WFF is valid?
a. $X$Y$Z ((P(X)->Q(Y))^(Q(Y)->R(Z)) ->
(P(X)->R(Z)))
b.
$Y%X (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.
11.
Which WFF is unsatisfiable?
a.
$X(P(X)) ^ ~P(a)
b.
%X$Y(P(X,Y)) ^ %Y$X (~(P(X,Y)))
c.
both.
d.
neither.
12. Which
WFF is stronger?
a.
$X(P(X)+Q(X))
b.
$X(P(X))+$X(Q(X))
c
neither.
d.
cannot tell.
The
next three questions are about the following language:
{ am bn cm |
m,n >=1 }
13.
This language is
a.
CF
b.
DCF
c.
both
d. neither.
14. This
language has infinitely many sufficiently long strings to
satisfy
a.
the CFL
Pumping Lemma.
b.
the Regular
Language Pumping Lemma.
c.
Both.
d. neither.
15.
This language can be accepted by
a.
a DPDA by the empty-stack.
b.
an NPDA by the empty-stack.
c. an NPDA by
the final state(s).
d.
All
above
e. two above.
f. none
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, 5)
(4, a, 5)
(4, b, 4)
(5, a, 4)
(5, b, 5) where each triple is (originating-state,
input-symbol, terminating-state)
and state-4 and state-5 are
accepting.
16.
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.
17. Which
two states are equivalent?
a.
2 and 3
b.
4 and 5
c. both.
d.
neither.
18. 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.
19. Which
is closed under both
a.
Type-3 (regular)
languages.
b.
DCFL’s
c.
CFL’s
d.
All
bove.
e. two above.
f. none
above.
All students are honest and hard-working.
20 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))
For
the next two questions, consider the initial input set of the following four
clauses:
C1:
P(X) + Q(f(X))
C2:
~Q(Y)
C3:
R(Z) + ~Q(c)
C4:
P(X) + ~S(V) + R(Z)
21.
Which two clauses can be resolved?
a.
C1 and C2
b.
C1 and C3
c.
C2 and C3
d.
all above.
e. two
above.
22.
Which is the resolvent of C1 and C2?
a.
P(f(X))
b.
P(X)
c.
both
23.
Which is solvable?
a.
CFG Ambiguity problem
b.
CFL Equivalence problem
c.
Regular language equivalence problem.
d.
all above.
e.
two above.
f. none
above.
24.
Which is solvable?
a.
CFL Infinity problem and CFL Membership problem
b.
CFL Emptiness problem.
c.
deciding whether or not the complement of a DCFL is a
DCFL.
d.
all above.
e.
two above.
f. none
above.
PART-B.
Other problems
(28 points)
Do three problems.
A.
{ an bn cm |
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.
B.
Give all clauses for:
$X$Y%Z (~(P(X)^~R(Z)) -> (S(Y)+Q(Z)))
C.
Give two DCFL’s whose union is
not a DCFL.
And give two CFL’s whose
intersection is not CF and give precise reason for that.
D.
Give a necessary and sufficient
condition for Regular Languages.
And, also give a necessary
condition for CFL’s.
E.
Prove that the following each is
not Regular.
a.
The set of strings of balanced
parentheses. These are the strings of “(“ and “)” that can appear in a
well-formed arithmetic expression.
b.
L = {0n | n is a prime}
F.
Derive and clearly show the
language accepted by the following DSFA with three states, 1, 2, and
3:
(1, a,
2)
(1, b,
1)
(2, a,
2)
(2, b,
3)
(3, a,
2)
(3, b,
1) where only
state-3 is accepting.
G.
Give a CFL that is not
deterministic.
And, show that it is not
deterministic.