Hints for Homework 6
---------------------

Problem 1

(a) See the "pumping lemma help" link, on lecture 9.

(b) L is clearly regular.   So the conclusion is correct.
But the justification is still wrong.

----------------------------------------------
Problem 2 

All three definitions talk about counting in a way that suggests
non-regularity.   But at least one of them is, in fact, regular.   
Think carefully about what strings are in each of the sets.

----------------------------------------------
Problem 3

See lecture 9 and the "closure properties" handout on lecture 6.

Your proof by contradiction should start with the assumption that
L (or J) is regular.   Use closure properties to deduce that T is
regular.   This contradicts the known fact that T is not regular.

Be sure to apply each closure property in the correct order:  if
certain input languages are regular, so is the output of the operation.


----------------------------------------------
Problem 4 (bonus)

If L is regular, it is recognized by some DFA.   You need to design an
NFA recognizing t(L).

Your new NFA needs to "process" x and the unknown string y in
parallel, to make sure they have the same length.  What can it guess
about the middle of the string, in order to allow it to get started,
right away, processing possibilities for y?


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