Hints for Homework 2

(1) Double-check that each state has exactly one outgoing
transition for each character in the alphabet.

(b) For example, 00000 is in L, but 0000 and 000000000 are not.

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

(2) (a) Once you find a description for the language, 
then see if you can simplify the description.

(b) Yes, the answer is a bit unexpected.   We really do mean this.

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

(3) Sets and Trees
(a) Don't panic when you look at the formula.   Try working
out its value for some small examples, and do the big examples
step by step.    Be careful about how many set brackets are
around each value at each step.

(b) The big Sigma sums over all the items in a set.   It's just
like the ones you've seen in calculus or discrete math, except that
you are summing over things from a set rather than over some
subrange of the integers.

(c) Is it true for the examples P and R? 


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

(4) Balanced strings
(a) Psuedo-code should look like a hybrid between code and mathematics.
Use the control features of code (e.g. for loops, if statements) but
omit details that only a compiler cares about (e.g. type declarations,
simple utility functions). Make sure it's easy for a human to read.

Model the style of your pseudo-code on the programming language you
are most comfortable with.   

(b) In the second lecture, we saw such an automaton for k=2.  Write
a general description of how to build something similar for any input
value of k.  Pick nice names for your states to make your description
easier to write.

(c) and (d) should require short, simple answers.   We aren't after
a proof but, rather, we want you to understand why it's true.

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

(5) This is a bonus problem, so feel free not to do it if you don't
have time or find it too hard.  

Describe the states the board might be in, and then decide how Jane's
moves affect the state of the system. Show how to get to the winning
configuration starting from each position.  Then try to combine these
different sequences into a single sequence.