COSC3302
Test-2
4/27/2011
Keys Used:
1-5:
DAAFD
6-10:
CAADF
11-14: DDEC
NAME__________________________________________________
THROUGHOUT THIS TEST, THE FOLLOWING
NOTATIONS ARE APPLICABLE:
1.
RE:
Recursively Enumerable
2.
PC:
Partially Computable
3.
S.L.
The Simple Language with the following three BASIC
instructions:
V = V+1
V = V-1
IF V <> 0 GOTO L
4.
NPDA
Nondeterministic pushdown automata.
5.
DPDA
Deterministic pushdown automata.
6.
CFG:
Context-Free Grammar.
7.
CFL:
Context-Free Language.
8.
DCFL:
Deterministic CFL.
9.
l:
The
empty-string.
PART-A:
Multiple Choice Questions.
(42 points)
1. Which
is Computable?
a.
Halt(x,y)
b.
F(X1,X2) = X1 + 2*X2
if X1> 2*X2
or
else undefined
c.
Both.
d.
neither.
2.
Which
is Partially Computable?
a. f(X1,X2)
= absolute value of X2-X1 if X2>X1 else undefined.
b.
f(X1,X2,X3)
= whether or not two programs, X1
and X2, both stop at the same
time upon taking the same input, X3.
c.
Both.
d.
neither.
3.
Which is a
DCFL?
a.
L1 = { am bn | m,n >=1 }
b.
L2 =
{w w | w is in (a+b)
* }
c.
both.
d.
neither.
4.
All CFL’s are equivalent
to
a.
all DPDA’s.
b.
all Type-2 Grammars.
c.
all CFG’s.
d.
all of above.
e.
a & b.
f.
none
5.
Which is CF???
a.
L1 = {bm cn |m,n>=0}
b.
L2 = {am bn cn dm
|m,n>=0}
c. L3
= {am bm dn |m,n>=0}
d. All
above.
e.
two.
f.
none
6.
Any CFL without the empty string in it can equivalently be represented
in
a.
CNF
b.
GNF
c. Both.
d.
neither.
7. 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 Final-State(s) acceptance and all DCFL’s
c. both.
d.
neither.
8.
Suppose that a family of languages is closed under Union and also under
Complementation.
In this
case,
a.
it must be closed under
Intersection.
b.
any proper subset of
this family is closed under Union.
c.
Both.
d.
neither.
9.
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.
10.
Which problem is solvable?
a.
STEP(x1,x2,x3,y,t)
b.
Membership problem for CFL
c.
Membership problem for RE sets.
`
d. all above.
e.
a & c above.
f.
none above.
11.
Which is unsolvable?
a. Halting
Problem
b. Equality
problem for RE sets.
c. Problem
of deciding whether or not the complement of a CFL is CF.
d. all above.
e. two above.
f.
none above.
12.
Which is an application of CFG or of CFL?
a. Compiler
design (parser)
b. RNA
Secondary Structure Prediction
c. Reverse
Engineering
d. all above.
e. two above.
13.
According to the Grammar of program-3 (Expression Parsing), which is a
legitimate expression?
a. (A)+B*C
b.
A+(B*C)
c. ()+B*C+B
d. all above
e.
two above.
14.
According to the Grammar of program-4, which nonterminal is nullable?
a. Exp and
SS
b. S and
Body
c. both.
d.
neither.
PART-B. Other problems.
(58 points)
Do five problems
in this PART.
1.
Give a CFL that cannot be accepted by a deterministic PDA and state the
precise reasons for that.
2.
Show that CFL are closed under Union but not closed under Intersection.
3.
Show that the following is each a Macro of the SIMPLE
Language:
V1 =
V2
V = 0
GOTO L
4.
L3 = {an bm cm
|m,n >= 1}
L4 = {am bn cm |m,n
>=1}
Prove or disprove that each language above is CF.
5.
Briefly describe various types of languages along with their
corresponding accepting devices.
And, indicate cases where determinism and non-determinism are NOT
equivalent (or seem to be
NOT
equivalent) and why.
6.
Convert the following CFG into the CNF and clearly show the
result:
S -> S R |
( R R )
R -> ( ) | ( S
)
7.
State the Pumping Lemma for CFL. And also how it can be
used.
8.
State exactly why the Membership question for R.E. sets is unsolvable.
9.
Give the definition of R.E. sets and Recursive
sets.
And, give an example of a Recursive set.