COSC3302
Final Exam.
5/7/2011
NAME__________________________________________________
THROUGHOUT THIS TEST, THE FOLLOWING
NOTATIONS ARE APPLICABLE:
1.
RE:
Recursively Enumerable
2.
PC:
Partially Computable
3.
FSA:
Finite State Acceptors (Deterministic or otherwise)
4.
S.L.
The Simple Language with the following three
BASIC
instructions:
V = V+1
V = V-1
IF V <> 0 GOTO L
5.
NPDA
Nondeterministic pushdown automata.
6.
DPDA
Deterministic pushdown automata.
7.
CFG:
Context-Free Grammar.
8.
CFL:
Context-Free Language.
9.
E.R:
Equivalence Relation.
10.
DCFL:
Deterministic CFL.
11.
l:
The
empty-string.
12.
$:
Universal Quantifier. (For all)
13.
%:
Existential quantifier. (For at least one)
14.
^:
Conjunction operator. (AND)
15.
+:
Disjunction operator. (OR)
16.
~:
Negation operator. (NOT)
17.
->:
Implication operator (IMPLIES)
18.
V,W,X,Y,Z:
A variable.
19.
a,b,c,d:
A constant.
20.
f,g,h:
A function.
21.
P,Q,R,S:
A predicate (in Predicate Calculus)
22.
A,B,C,D:
A Literal (in
Propositional Calculus)
PART-A:
Multiple Choice Questions.
(114 points)
First 3 questions are
about the following binary relation:
1 0 0 0
1 1 0 0
0 0 1 1
0 0 0 0
1.
The
relation is
a.
reflexive
b.
symmetric
c.
transitive
d.
All
above
e. Two above
f. None
2.
The
relation is
a.
Antisymmetric
b.
Irreflexive
c.
Both.
d.
Neither.
3.
Which
is its minimum E.R.?
a.
1 1 1 0
b.
1 1 1 1
c.
1 1 0 0
1 1 1 0
1 1 1 1
1 1 0 0
1 1 1 0
1 1 1 1
0 0 1 1
0 0 0 1
1 1 1 1
0 0 1 1
d.
None
4.
Which
is a Clause in the Predicate Calculus?
a.
P(x)
+ Q(y) + ~R(y)
b.
~(P(x)
^ Q(x))
c.
Both.
d.
neither.
5.
Which is equivalent to:
A -> B -> C
a.
A
-> (B -> C)
b.
(A
-> B) -> C
c.
Both.
d.
neither.
6.
Which is equivalent to:
$X(P(X) ^ Q(X))
a.
$X
P(X) ^ ($Y Q(Y))
b.
$X
P(X) ^ ($X Q(X))
c.
both.
d.
neither.
7.
Which is equivalent to:
%X(P(X) + Q(X))
a.
%X
P(X) + (%X Q(X))
b.
%X
P(X) + (%Y Q(Y))
c.
both.
d.
neither.
8.
Which is implied by:
$X$Y (P(X,Y))
a.
%Y%X
(P(X,Y))
b.
$X$Y
(P(Y,X))
c.
both.
d.
neither.
9.
Which is implied by:
%X (P(X) -> Q(X))
a.
%X
P(X)
b.
$X
P(X) -> (%Y Q(Y))
c.
both.
d.
neither.
10.
Which is a tautology?
a.
A
^ B -> D
b.
A
^ B -> A
c.
A
^ B -> B +
D
d.
b
and c above
e.
a and b above.
11.
The Pumping Lemma of Regular languages is
a.
a necessary condition useful
in showing that a language under consideration is regular.
b.
a necessary condition useful
in showing that a language under consideration is not
regular.
c.
a sufficient condition
useful in showing that a language under consideration is
regular.
d.
a sufficient condition
useful in showing that a language under consideration is not
regular.
Next
three questions are about the following non-deterministic FSA where Q1 is the
Initial state and it is
the
only Accepting state:
|
|
l |
a |
b |
|
Q1 |
Q2 |
Q3 |
Q2 |
|
Q2 |
Q3 |
Q1 |
Q2 |
|
Q3 |
|
Q1 |
Q2 |
12.
The empty-closure of Q1 is
a.
{Q1, Q2}
b.
{Q1, Q2, Q3}
c.
{Q2, Q3}
d.
none above.
13.
For an equivalent deterministic FSA, the Initial sate is the combination
of
a.
{Q1,
Q2}
b.
{Q1, Q2,
Q3}
c.
{Q1}
d.
None
above
14.
Which string is accepted by this acceptor?
a.
l
b.
aaaa
c.
bbbb
d.
all above.
e.
two above.
**********************END-OF-NFSA-REFERENCE*************************
15.
Which is equivalent to:
(a + b)* (b + a)
a.
a (a + b)* + b (a + b)*
b.
a (a + b)* + b a* (a + b)*
c.
both.
d.
neither.
16.
Which language on the alphabet of {a,b} is Regular?
a.
all strings with an even number of
b’s.
b.
all strings that start with so many a’s followed by exactly as many
b’s.
c.
all strings that start with so many a’s followed by any number of
b’s
d.
all above.
e.
a and c above.
f.
b and c above.
17.
An FSA is truly non-deterministic if
a.
a state has just one outgoing transition and it is on the
empty-string.
b.
a state has two different destination states on the same input
symbol.
c.
a state has the same destination state on the Empty-string and on an
input symbol.
d.
all above.
e.
a and b above.
f. b and c above.
18. Which
is Computable?
a.
Halt(x,y)
b.
F(X1,X2) = X1 +
2*X2
c.
Both.
d.
neither.
19. Which
is Partially Computable?
a. f(X1,X2)
= absolute value of X2-X1 if X2>X1 else undefined.
b.
Halt(X1,X2,y) = whether
or not a program y stops eventually on taking two inputs, X1 and X2.
c. Both.
d.
neither.
20.
Which is a DCFL?
a.
L1 = { am bm | m >=1 }
b.
L2 =
{w w | w is in (a+b)+ }
c.
both.
d.
neither.
21. CFL’s are closed
under
a.
Union
and Concatenation.
b.
Complementation.
c.
Both.
d.
neither.
22. All CFL’s are equivalent
to
a.
all DPDA’s.
b.
all Type-2 Grammars.
c.
all CFG’s.
d.
all of above.
e.
two.
f.
none
23. Which is
CF???
a.
L1 = {bm cn |m,n>=0}
b.
L2 = {am bn cn dm
|m,n>=0}
c. L3
= {am bm cm dn |m,n>=0}
d. All
above.
e.
two.
f.
none
24.
Any CFL without the empty string in it can equivalently be represented
in
a.
CNF
b.
GNF
c. Both.
d.
neither.
25. 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.
26.
Suppose that a family of
languages is closed under Union but NOT under
Complementation.
In this case,
a.
it must not be closed under
Intersection.
b.
any proper subset of
this family is closed under Union.
c.
Both.
d.
neither.
27. All
Regular Languages are equivalent to
a. all
DFSA’s
b. all
NFSA’s
c. both.
d.
neither.
28. 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.
29.
Which pair is equivalent?
a. (A -> B)
(~A + B)
b. A ^
(A+B)
A
c. both.
d.
neither.
30.
Which pair is equivalent?
a. ~($x P(x))
%x(~P(x))
b. $x$y (P(x,y))
$y$x (P(x,y))
c. $x%y (P(x,y))
%y$x (P(x,y))
d. all above.
e. two above. f. none
above.
31.
Which problem is solvable?
a.
STEP(x,y,t)
b.
Membership problem for CFL
c.
Membership problem for RE sets.
`
d. all above.
e. two above.
f.
none above.
32.
Which problem is solvable?
a.
Emptiness problem for Regular languages.
b. Totality
problem for Regular languages.
c. both.
d.
neither.
33.
According to the Grammar of Program-3 (Expression Parsing), which is a legitimate
expression?
a.
((A))+B*C
b.
(A+B))*C
c. both.
d.
neither.
34.
According to the Grammar of Program-4 (CFG Reduction), which nonterminal
is nullable?
a.
Exp
b.
Body
c.
Program
d. all above.
e. two above.
f.
none above.
35.
According to the Grammar of Program-4 (CFG Reduction), which nonterminal
is useless?
a.
More
b.
Another
c.
SR
d. all above.
e. two above.
f.
none above.
36.
Which is an application of Regular grammars or Regular
expressions or DFSA?
a. Compiler
design (Scanner)
b. ALU
Adder/Multiplier design
c. DNA
testing
d. all above.
e. two above.
37.
Which is an application of CFG or of CFL?
a. Compiler
design (Parser)
b. Reverse
Engineering
c. both.
d.
neither.
38. When
is a sentence of a CFL ambiguous?
a. there are two distinct
parse trees for the sentence.
b. there are two distinct
leftmost derivation sequences for the sentence.
c. both.
d.
neither.
PART-B. Other problems.
(86 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 q3 is accepting)
|
State/input |
a |
B |
|
q1 |
1 |
2 |
|
q2 |
3 |
2 |
|
q3 |
3 |
2 |
Derive and clearly show the
language accepted by the above FSA.
2. Prove or disprove
that the following language is Regular:
L =
{ am bn
| m,n
>= 1}
3. Convert the following to the CNF
(Conjunctive Normal Form) and to the DNF (Disjunctive Normal Form),
respectively:
(A+B+C) -> (D+E)
4. Give
a Regular grammar or a FSA for the following language: L2 = (a +
b)* (d + c).
5.
L3 = {am bm cm |m
>= 1}
L4 = {am bn cm
|m,n>=1}
Prove or disprove that each language above is CF.
6. List
some applications of DFSA/FSA/Regular-Grammars/Regular-Expressions.
7.
Prove that either the Predicate HALT(x,y) or the Membership Problem for RE sets is
Unsolvable.
This
Predicate is, of course, determines whether or not an arbitrary program y
eventually
stops upon taking an input x.
8. Give
an Adjacency Matrix for the smallest binary relation over the set A ={a,b,c,d}
for each of the following 3
cases:
a. Symmetric and Reflexive and Transitive.
b. Anti-symmetric but not Reflexive.
c.
Not Reflexive and not Irreflexive.
9.
Convert the following CFG into the CNF and clearly show the
result:
S -> S R
S -> ( P R )
P -> ( R )
R -> ( )
R -> ( S )