PROBLEM SET 6, CSC 280, 2006
DUE BEFORE CLASS, WED. MAR. 8
The sixth problem set is as follows. All 7 problems will be marked out
of the same total. Answers to any 6 questions make a complete answer
paper. However, you can do all questions to earn bonus points.
Note that whenever you are asked to design a TM, what is meant is
a 1-tape deterministic TM, unless specified otherwise.
Keep your eyes on the instructor's and the TAs' web site for any corrections
or discussion.
PROBLEM 1
~~~~~~~~~
a. Prove that {| A is a DFA s.t. L(A) is infinite} is decidable, using
a proof that is directly based on the state transition diagrams of
DFAs (rather than on use of the emptiness decider for DFAs, as in
Sipser's proof on p.185).
b. Prove that SUB_dfa defined as {| A, B are DFAs s.t. L(A) is a
subset of L(B)} is decidable. You can use theorems taken in class.
Problem 2
~~~~~~~~~
a. Show that #CFG[>n], defined as {| G is a CFG and ||L(G)|| > n},
is decidable for n = 0, 1, 2, ...
b. Show that INT_cfg, defined as {| G, G' are CFGs & L(G), L(G')
are not disjoint} is Turing-recognizable (recursively enumerable).
Problem 3
~~~~~~~~~
Prove that #CFG[| G is a CFG and ||L(G)|| < n},
is decidable for n = 1, 2, 3, ... (Hint: We can bound the derivation
length for nonrecursive CNF grammars.)
PROBLEM 4
~~~~~~~~~
a. Construct a TM (as a state transition diagram, omitting transitions
to dead-end states) for recognizing {w^n | n >= 1 and w is a string
of form 21...1, i.e., one 2 followed by one or more 1's}. Keep it
as simple as you can.
b. Construct (as a state transition diagram) a NTM for recognizing
{1^n | n is not an odd prime}, keeping the machine as simple as
possible. Suggestions: Make use of the machine in (a), and also
employ nondeterminism to try to achieve simplicity. (The instructor's
solution is a 7-state machine using symbols 0,1,2,#, discounting
dead-end states; perhaps you can find a simpler one.)
PROBLEM 5
~~~~~~~~~
A context-sensitive grammar is a quadruple G = (V, Sigma, R, S) where
V, Sigma, and S are defined as for CFGs, but rules in R are of form
x -> y,
where x, y are strings that can use both variable and terminal symbols,
except that the RHS y must be at least as long as the LHS x. If the
start symbol S does not occur on the RHS of any rule, then a rule
S -> e
is permitted as well, where e is the empty string. Derivations start
with S and are defined much as for CFGs, except that now a step of a
derivation is of form vxw => vyw, where x -> y is a rule. Any derivable
terminal string is considered to be in L(G).
Design context-sensitive grammars for (a) {ww | w is in {0,1}*} and
(b) {a^ib^ib^ic^i | i is an integer >= 0}.
PROBLEM 6
~~~~~~~~~
a. A universal TM is a TM which, given as input where M is a TM,
accepts [rejects] the input if M accepts [rejects] w, and does not
accept the input if M fails to terminate on w. (It also rejects
inputs that are not of form .) In other words, it behaves for
essentially as M would behave for w.
Prove that if U is a universal TM, then {w | U halts on w} is
undecidable.
b. Prove that if M is a TM that recognizes an undecidable language,
then {w | M halts on w} is undecidable.
PROBLEM 7
~~~~~~~~~
Prove that determining whether a TM eventually prints a 1, i.e.,
{| M is a TM which eventually prints a 1 given input w} is
undecidable.