COSC3302
Final Exam.
5/8/2007
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.
7. DPDA
Deterministic pushdown automata.
8. CFG:
Context-Free Grammar.
9. CFL:
Context-Free Language.
10. DCFL: Deterministic
CFL.
11. l:
The
empty-string.
PART-A. Multiple Choice
Questions.
(78 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
d.
All.
e. two.
f.
none.
2.
Which
is Solvable?
a.
Halting
Problem.
b.
CFG
Ambiguity 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.
F(X1,X2)
= X1 + 2*X2
c.
Both.
d.
neither.
5.
Which
is Partially Computable?
a.
f(X1,X2)
= absolute value of X1-X2 if X1>=X2 else undefined.
b.
f(X1,X2,X3)
= whether or not two programs, X1
and X2, both stop always at the same
time upon taking the same input, X3.
c.
Both.
d.
neither.
6.
Which is a DCFL?
a.
L1 = { am
bn | m,n
>=1 }
b.
L2 = {w c w | w is in (a+b) *
}
c.
both.
d.
neither.
7.
CFL’s are closed
under
a.
Intersection.
b.
Complementation.
c.
Both.
d.
neither.
8.
All CFL’s are equivalent
to
a.
all
NPDA.
b.
all
DPDA
c.
all
CFG’s.
d.
all of above.
e.
two.
f.
none
9.
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
10.
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.
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
Q2
B
B
Q2
Q4
B
1
Q5
//Successful terminating condition
Q4
1
R
Q3
//Quad-6
Q3
B
B
Q3
//Quad-7
11.
This
TM does not stop if the input string
a.
is
the empty-string.
b.
has
an odd number of ones.
c.
Both.
d. neither.
12.
When
this TM stops, it is computing
a.
F(x)
= x+1
b.
F(x)
= x+2
c.
Neither.
13.
The
purpose of quadruple-7 above is
a.
to
stop thereby completing the computation of the function.
b.
to
enter an infinite loop thereby refusing to complete the computation of the
function.
c.
Both.
d.
neither.
14.
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
15. Any
CFL without the empty string in it can be represented by
a.
CNF
b.
GNF
c.
Both.
d.
neither.
16.
Which
pair is equivalent?
a.
all
NPDA’s with the Empty-Stack acceptance and those with Final-State(s)
acceptance
b.
all
NPDA’s with the Empty-Stack acceptance and all DCFL’s
c.
both.
d.
neither.
Next four questions are
about the following CFG:
S -> S R
S -> ( R
)
R ->
P Q
Q -> (
)
Q -> ( Q
)
Q ->
P
P ->
R
P ->
17. Which
string is in the language generated by this CFG?
a.
l
b.
(
( ) ) ( )
c.
(
( ) ) ( ( ) ) ( )
d.
All.
e.
two.
f.
none.
18.
Which non-terminal is Nullable?
a.
P
b.
Q
c.
R
d.
All.
e.
two.
f.
none.
19.
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 =
v = “(“
v =
“(“
w = ”()”
w =
“()”
x = “)”
x =
“)(“
y = “(())”
y = “())(())”
c.
both.
d.
neither.
20.
Which production rule is to be included when all unit productions are
eliminated?
a.
S -> S P and S -> S Q
b.
S -> ( P ) and S -> ( Q )
c.
both.
d.
neither.
21. Suppose that a
family of languages is closed under union but NOT under intersection. In this
case,
a.
it may or
may not be closed under complementation.
b.
Any proper
subset of this family is closed under union.
c.
Both.
d.
neither.
Next three questions are about the following
DFSA:
|
|
A |
b |
|
Q1 |
Q2 |
Q4 |
|
Q2 |
Q2 |
Q3 |
|
Q3 |
Q2 |
Q4 |
|
Q4 |
Q4 |
Q4 |
Q3 is accepting
22.
Which string is accepted by this DFSA?
a.
l
b.
aaba
c.
aababa
d.
all.
e. two.
f.
none.
23.
Suppose that the following string is sufficiently
long:
aaaba
In this case, which decomposition of this string into three parts will
satisfy the Pumping Lemma of
Regular
Languages?
a.
u = ‘a’
b.
u = ‘aa’
v = ‘a’
v = ‘ab’
w = ‘aba’
w = ‘a’
c.
both.
d.
neither.
24.
This acceptor is
a.
completely
specified
b.
deterministic
c.
both.
d.
neither.
25.
All Regular Languages are equivalent to
a.
all
DFSA’s
b.
all
NFSA’s
c.
both.
d.
neither.
26.
An NPDA will accept an input string when
a.
its
stack becomes empty without necessarily completely scanning the input
string.
b.
it
enters a final state without necessarily completely scanning the input
string.
c.
Both.
d.
neither.
PART-B. Other
problems.
(80 points)
Do all problems
in this PART.
1.
Consider the
following FSA with three states {q1,q2,q3) and two input symbols{a,b}:
(only
q2 is accepting)
|
State/input |
a |
b |
|
q1 |
1 |
2 |
|
q2 |
1 |
3 |
|
q3 |
2 |
3 |
Derive and
clearly show the language accepted by the above FSA.
2.
Show the following
language is not Regular:
L = {
am bn cm
| m,n >=
1}
3.
Consider the
following argument:
P1: Every dog
either likes people or hates cats.
P2: Rover is a
dog.
P3: Rover does
not hate cats.
C:
Therefore, some dogs like people.
Using the following
predicates, show that the argument is logically valid using the
Resolution
Procedure:
D(x): x is a
dog
L(y): y
likes people
H(z): z
hates cats
4.
Convert the
following to the CNF (Conjunctive Normal Form) and to the DNF (Disjunctive
Normal Form), respectively:
(A+B+C) -> (D^E+D)
5. Give a Regular
grammar for the following language: L2 = (a +
c)* (a + b) (b + c).
6.
L3 = {am bm cm |m >= 1}
L4 = {am bn cm+n
|m,n>=1}
Prove or disprove that each language above is CF.
7.
Give a CFL that cannot be accepted by a deterministic PDA and state the precise reasons for
that.
8.
Give an NPDA that accepts by the Final-State(s) the following
language:
L5 = {w 2 wr |w is a non-empty string of 0’s and
1’s}
This language has strings like 0012100, 01210, 0112110, 020, 121,
10201,
11211, 1102011, 110020011, and so on.
9.
Give a program which the Predicate HALT(X,X) would
contradict.
And, then describe some key points for that.
10.
List various types of languages along with their characteristics
and
corresponding accepting devices.
And, indicate cases where determinism and non-determinism do not
equal
and brief reasons of why they do not.
11.
Convert the following CFG into the CNF and clearly show the
result:
S -> S R
S -> P R
R
P -> ( R
)
R -> ( )
R -> ( S
)