Date: Wed, 08 Jan 1997 20:37:25 GMT Server: NCSA/1.4.2 Content-type: text/html
Think of L as the set of arbitrary shuffles of strings from and
. For example, if aab is in
and bb is in
then
the strings aabbb, ababb, bbaab and many other strings are in L.
Hint: The machine will have to run both
and
in parallel, but
only one at a time. Thus, a cross product-like construction is in order.
You don't have to prove that your construction is correct, but you must state a behavioral lemma which could be used in such a proof.