COCS5340 Final 12/11/2001.
Name_______________________________________
THROUGHOUT THIS TEST, THE FOLLOWING NOTATIONS ARE APPLICABLE:
1. $: Universal Quantifier.
2. %: Existential quantifier.
3. ^: Conjunction operator. (AND)
4. +: Disjunction operator. (OR)
5. ~: Negation operator. (NOT)
6. ->: Implication operator (IMPLIES)
7. T,U,V,W,X,Y: A variable.
8. a,b,c: A constant.
9. f,g,h: A function.
10. P,Q,R,S: A predicate.
11. #: The Empty-symbol
PART-A. True/False Questions (80 points)
For the first five questions, refer to the following DPDA, M:
(Q0, a, Z) -> (Q1, XZ)
(Q1, a, X) -> (Q1, XX)
(Q1, b, X) -> (Q1, #)
(Q1, c, Z) -> (Q2, Z)
(Q2, c, Z) -> (Q2, Z) where Q2 is the accepting state.
1. If we exchange the accepting state with non-accepting
states, the resulting acceptor will accept the complement of
L(M)
2. Any string in L(M) must have exactly as many a's as b's.
3. The following grammar defines L(M):
S -> a R b R C
R -> a R b R | #
C -> c C | c
4. The above CFG can be converted into an equivalent unambiguous
grammar if it is ambiguous.
5. The complement of L(M) is also CF.
***************END-OF-DPDA-REFERENCE*********
6. The following two clauses can be resolved:
P(X,Y) + Q(T,Y)
~P(a,b) + ~Q(a,f(U))
7. The resolvent of any two given clauses is logically
equivalent to the conjunction of the two clauses rather than
following from their conjunction.
8. Each of the following is a clause:
P(a)
P(a) + Q(b)
P(a)^Q(X)
9. P(T) is the resolvent of the following two clauses:
P(T)+Q(T)
~Q(a)
10. If the Emptiness Problem of DCFL's is decidable, then so is
that of their complements.
11. If the complement of a CFL L is not CF, then L is not a
DCFL.
12. Every DCFL with or without the Prefix Property has an LR(0)
grammar defining it.
13. DCFL's are closed under each of:
Union
Complementation
MAX
Intersection with Regular sets
14. DCFL's are equivalent to LR(0) Grammars.
15. DCFL's are closed under any operation under which CFL's
are closed as they are a subset of all CFL's.
16. The Normal Form for DPDA's is also applicable to NPDA's.
17. The Predicting Machine of a DPDA M and a DFSA A accepts
the same language as M.
18. Given a DPDA, we can find an equivalent DPDA that scans
any possible (but legitimate) input string in its entirety.
The same can be said to any given NPDA.
19. Given a NPDA by Final-State acceptance, it is decidable
whether or not a final state reaches another final state (including
itself) by consuming at least one input symbol.
20. The Final-State acceptance and the Empty-Stack acceptance
are equivalent for NPDA's but not for DPDA's.
PART-B. Multiple Choice Questions.
1. Which is complete?
a. Unit Preference
b. Input Strategy
c. AF-Form Strategy d. All e. Two. f. None
2. Which two clauses can be resolved?
a. ~P(X) + Q(X)
P(a) + Q(f(T))
b. ~P(a) + Q(Y)
R(X) + ~Q(X) c. Both. d. Neither
3. In the AF-Form strategy, two clauses can be resolved when
a. both are an input clause.
b. one is an ancestor of the other.
c. just one is an input clause.
d. All. e. Two. f. None
4. ~P(X) + Q(X)
P(a) + R(Y)
A resolvent of above two clauses is
a. Q(X) + R(Y)
b. Q(a) + R(Y) c. Both. d. Neither.
5. %X (P(X) -> Q(X))
($X(P(X))) -> %X(Q(X))
a. First implies the second.
b. Second implies the first.
c. Two are equivalent. d. None
6. $X%Y (P(X) -> Q(Y))
%Y$X (P(X) -> Q(Y))
a. First implies the second.
b. Second implies the first.
c. Two are equivalent. d. None
7. $X ($Y(P(X,Y) -> P(X,a)))
Which is a model for above?
a. P(X,Y)=(X=Y) and D={a,b}
b. P(X,Y)=(X<>Y) and D={a,b} c. Both. d. Neither.
8. %X ($Y(P(X,Y) -> P(X,a)))
Which is a model for above?
a. P(X,Y)=(X=Y) and D={a,b}* NOTE * is a superscript.
b. P(X,Y)=(X<>Y) and D={a,b}*
c. Both. d. Neither.
9. Which Semi-Thue process has a solvable Word problem?
a. a->aa b. a->aa c. ab->ba
b->bb aa->a ba->ab
b->bb
bb->b
d. All. e. Two. f. None
10. CSL's without the Empty-String are closed under
a. Union and Intersection, each.
b. Complementation (without inducing the Empty-String)
c. Set Difference (A-B) d. All. e. Two
11. For a given arbitrary CSG G, which is solvable?
a. Ambiguity problem.
b. whether an arbitrary string is in L(G)
c. whether L(G) is empty.
d. All. e. Two. f. None.
12. For a given arbitrary grammar G, which is solvable?
a. whether an arbitrary string is in L(G).
b. whether L(G) is infinite.
c. whether L(G) is Recursive.
d. All. e. Two. f. None.
13. For a given arbitrary DTM M, which is solvable?
a. SIGMA(M) Word problem.
b. THETA(M) Word problem.
c. whether L(M) is RE.
d. All. e. Two. f. None
14. For a given arbitrary DTM M, which is solvable?
a. whether M stops on the empty input string.
b. whether M stops on an input string that represents
M itself.
c. whether M reaches an arbitrary state of its own on
an arbitrary input string.
d. All. e. Two. f. None.
15. For a given arbitrary NDTM M, which is solvable?
a. whether any one possible sequence of moves accepts
an arbitrary input string.
b. whether every possible sequence of moves accepts
an arbitrary input string.
c. Both. d. Neither.
16. For a given arbitrary LBA M, which is solvable?
a. whether the Empty-String is in L(M).
b. whether L(M) is empty.
c. whether L(M) includes all possible strings on the
input alphabet except the Empty-String.
d. All. e. Two. f. None.
17. For given two LBA M1 and M2, which is solvable?
a. whether L(M1).L(M2) (their concatenation) is CS
b. whether L(M1)^L(M2) has the Empty-String.
c. whether L(M1)^L(M2) is empty.
d. All. e. Two. f. None.
PART-C. Other problems (40 points)
A. In no more than 12 lines, give some key ideas behind
reducing a Word problem to a PCP.
B. Consider the following argument:
Suppose we have a non-empty set S of some languages.
If this S is closed under
a. complementation and
b. union, respectively,
then it is also closed under intersection.
Prove this argument by the Resolution.
Use the following functions:
1. U(L1,L2) for the union of two lanuages L1 and L2.
2. Int(L1,L2) for the intersection of the two languages.
3. Comp(L1) for the complement of L1
Note that U(L1,L2) = Comp(Int(Comp(L1),Comp(L2)))
and Int(L1,L2) = Comp(U(Comp(L1),Comp(L2)))
Use the following predicate plus some others you need:
In(L) to mean that L is in the set.
C. L = {ambncK | m,n,k>=1 and (k<=m or k<=n)}
Note that m,n,k are each a superscript.
Show that L, above, is a CFL but that MAX(L) is not
D. Consider the following argument:
P1: ($X$Y) (P(X,Y) -> P(Y,X))
P2: ($T$U$W) (P(T,U)^P(U,W) -> P(T,W))
P3: ($V%Z) P(V,Z)
Conclusion: ($X) P(X,X)
Show that the argument is valid by Resolution.
E. Give a CFL that is not a DCFL.
And, show that it is, in fact, not a DCFL.