1. part (a) a*b(a U ba*b)* or (a U ba*b)*ba*
    Part (b) One of the possible solution is
    ((aUb)a*b(ba*b)*a)*((aUb)a*b(ba*b)*)*

2. Part a: You can either use Myhill-Nerode or pumping lemma to prove.
    For pumping lemma, the idea is that S(n) can be written as n(n+1)/2.
    If we choose string s = xyz = 0^{S(2p)}, then |s| = 2p^{2} + p.  If we
    pump the string to xyyz, then
    S(2p) = 2p^2 + p < |xyyz| <= 2p^2 + 2p < S(2p+1) = 2p^2 + 3p + 1.
    Therefore, xyyz is not in the language.

    For part b, you can use the similar idea, but instead of sum of the
    first n-th natural numbers, it's n-factorial. You can pick string s to
    be 0^{P(p)}, |s| = p! > p, then if you pump it to xyyz, then
    p! < |xyyz| <= p! + p < (p+1)p!

3. Part (a): This one is very similar to the proof for language of
    O^{n}1^{n}. I won't go to the detail about it. Choose s = 0^{p}10^{p}
    to avoid proving for multiple ways of breaking down s to x,y,z
    components.

    Part (c): Let W be the language in question. If W is regular, then W'
    (complement), which is basically the language of palindromes, must also
    be regular under the closure of class under complement. We have showned
    in class that W' is non-regular. Therefore, we've reached a
    contradiction, and thus W cannot be regular.

    Part (d): If you choose to prove by pumping lemma, then it will not be
    possible to prove by choosing string s = 0^{p}10^{p} or any string with
    similar format. The reason being that, once you pump this string, up or
    down, then it will still be in the language of L = {wtw}. Because,
    then, the extra 0's will become part of t.

   To illustrate, consider a string

   s = 0^p 11 0^p.

   For simplicity, we can think of w = 0^p, and t = 11.

   Then, if we pump the string up to xyyz, we get

   xyyz = 0^p 0^k 11 0^p, where 1 <= k <= p.

    This is not the same as part (a). Here, you can think of w = 0^p, and t
    becomes 0^k 11. Thus, xyyz is still in the language.

    So how to make this work? You can choose string s = 0^{p}1010^{p}1, and
    then pump it UP.

4. (a) You can use Myhill-Nerode thm, or use the closure properties to
    show that F is not regular.

   Important: For people who use the closure properties.

   Please remember that we want to prove that F is not regular.

    Let # represent a regular operation.
    Let languages A and B be regular, and C be non-regular.

   We know that, if F = A # B, then F is regular.

   However, if F = A # C, we cannot conclude that F is non-regular.

   But, we can conclude that F is not regular, if C = A # F.

    (b) You can show that F is pumpable by following the steps for pumping
    lemma. Pump a if i>=1, pump b if i=0.

    (c) The theorem states that all regular languages can be pumped, which
    does not imply that all pumpable languages are regular. Thus, Pupming
    Lemma cannot be used to prove the regularity of a language. It can only
    be used to prove irregularity of a language.