COCS5315 Test-2 12/18/2005.
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: A constant.
9. f,g,h: A function.
10. P,Q,R,S: A
predicate Symbol.
11. l: The Empty-symbol
Name (PRINT)_______________________________________
PART-A. Multiple
Choice questions (88
points)
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 nine quadruples.
Note that this TM, M, has 4 states, q1, q2, q3, and q4, on
the alphabet, {a,b},
and the only accepting combination is (q4,
B).
N1: q1 B R q2
N2: q2 a R q3
N3: q3 b R q3
N4: q3 a R q4
N5: q4 a a q4
N6: q4 b b q4
N7: q2 b b q2
N8: q2 B B q2
N9: q3 B B q3
1. Which
production is included in the equivalent W(M)?
a. a q3 b ->
q2 a b
b. a q3
B h ->
q2 a h
c. q5 B
-> q4 B
d. All. e. Two. f. None
2.
Which
production is included in the equivalent S(M)?
a. q0 B
-> q0
b. q3 a
-> q4 a
c. q1 B
b -> B
q2 b
d. all
above. e. two above. f. none above.
For the next three questions,
assume that the following is the input string:
a b a
3. In this case, which Post Word can
be derived by the equivalent S(M)?
a. h B q2 a b a h
b. h B a b a q4 B h
c. h q0 h
d. all above. e.
two above. f. none.
4. In this case, which Post Word can
be derived by the equivalent grammar?
a. h b
b b q0 h
b. h q0 h
c. h b
b b q5 a
a h
d. all. e. two. f. none.
5.
In this case, which string can be
derived by the equivalent grammar?
a.
h q5 a
b a h
b.
h a
b a q5 h
c.
a b
b b b a
d.
all above. e. two. f. none.
6. Which string is accepted by this TM?
a. a a
b. a b a
c. a b b a
d. all above. e. two. f. none.
Next three questions are about a
S.T. P (Semi-Thue Process) on the alphabet {a} with the following
six productions: aa -> aaa // p-1
aaa -> aaaaa // p-2
aaaa -> aaaaaa // p-3
aaaa -> aaa // p-4
aaaaa -> aaaa // p-5
aaa -> a // p-6
7. Which production can be eliminated without changing
possible derivations?
a. p-1 alone
b. p-2 alone
c. p-3 alone d. All e.
Two f. None.
8. Which derivation is possible?
a. aa ->
aaa
b. aa ->
aaaa
c. a ->
aaaaaa d. All. e. Two. f. None
9. Which production can be eliminated without changing
possible derivations?
a. p-4
alone
b. p-6
alone
c. both p-4
and p-5 d. all. e. two. f. none.
Next four questions are about the following CFG (Context-Free Grammar):
S -> P a Q
S -> R S
S -> b P b
R -> T T
T -> T Q
T -> P Q
P -> Q S Q
P -> Q
Q
-> l
Q -> P b Q
10. Which non-terminal is Nullable?
a. Q and P
b. T and R c. both. d. neither.
11. Which is an implicit (implied) Unit-Production Rule?
a. T -> Q
b. T -> P
c. S -> R 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 Q 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 -> b Q b
d. All above. e. two above. f. none above.
14. Which pair is equivalent?
a. All NFSA’s and all DFSA’s
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.
15. Which is solvable?
a. deciding
whether or not an arbitrary CSL is accepted by a non-deterministic LBA.
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.
16. Which is solvable for an arbitrary
grammar G where u and v are each an arbitrary string of
grammar symbols?
a. u ->
v (exactly one step derivation)
b.
deciding whether or not L(G) includes a sentence
of length at least k where k is a given
positive integer.
c. deciding
whether or not L(G) includes an arbitrary string of terminals.
d. all
above. e. two above. f. none
above.
17. 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.
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 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.
20. 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.
21. Which WFF is stronger?
a.
$X(P(X)+Q(X))
b. $X(P(X))+$X(Q(X))
c.
neither. d. cannot
tell.
$X%Y
(P(X)+Q(X) -> R(Y))
22. Which clause is included in the above WFF ?
a.
~P(X)+R(a)
b. ~Q(X)+R(f(X))
c.
~P(X)^~Q(X) + R(Y) d. all. e. two. f. none.
PART-B. Other
problems (12
points)
Do two
problems.
A. Consider the following PCP problem.
baba aba
ba baa
abab baba
Do you think
that this PCP instance has a solution. Be specific about your reasons.
If there is a
solution, prove and show it.
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 cn | m,n.>=1 }
c.
{ am
bn cn dm
| m,n.>=1 }
D.
Give
two CFL’s whose intersection is not CF.
And,
show that it is indeed not CF.