Hints for Homework 12
---------------------

(1) That is, give an algorithm that takes an encoding of a NFA <D> and
a number k and determines whether D accepts any strings of length <= k.

Give your answer in pseudo-code.  

Don't worry about the exact representation of the number k, e.g. unary vs.
binary.  That's too much detail.


--------------------------------------

(2) Your enumerator will probably have several working tapes, in addition to
the special output tape.  

Don't worry about the exact format of the output (e.g. what character is used
to separate successive strings).  That's too much detail.

--------------------------------------

(3) (a) See the material in lecture 20, section 2 and/or Sipser
p. 170-171.  Use the examples in these sections as a guide for how
much detail to include in your pseudo-code.  This algorithm is more
complex than the one in problem (2), so you will probably not include
as many fine details.

(b) and (c) None of these questions is tricky and you only need very brief
answers. The point is to help you get on top of the terminology.  E.g.
what *was* the difference between recognizable and decidable?