===========================================================================
CSC 236           Homework Exercise 6 -- Sample Solutions       Winter 2008
===========================================================================


1.  (a) 010 in L((\epsilon+1)0*1*0):
        pick \epsilon in L(\epsilon+1), 0 in L(0*), 1 in L(1*), 0 in L(0).

    (b) 010 notin L(0(11)*0):
        each string in L(0(11*)0) has an even number of 1's, but 010 has an
        odd number of 1's.

    (c) 010 in L((0*1*)*):
        pick 01 in L(0*1*) (0 in L(0*), 1 in L(1*)) and 0 in L(0*1*) (0 in
        L(0*), \epsilon in L(1*))

    (d) 010 notin L((0+1)(0*+1*)):
        by distributivity, (0+1)(0*+1*) == 0(0*+1*) + 1(0*+1*) == 00* + 01*
        + 10* + 11*, and 010 notin L(00*) (no string in L(00*) contains a
        1), 010 notin L(01*) (no string in L(01*) contains a 1 followed by
        a 0), 010 notin L(10*) (no string in L(10*) contains a 0 followed
        by a 1), and 010 notin L(11*) (no string in L(11*) contains a 0).


2.  (a) L_1 = { s in {a,b}* : s contains the substring bb }

         -  FSA:  Only need to remember last symbol read, more precisely,
                whether or not last symbol read was 'b'.  Construction:
                Put down initial state (with meaning "last symbol not b"),
                then add transitions one by one, creating new states as
                needed.  Repeat for each new state.  Then, figure out which
                states should be accepting.

                Transition diagram in ASCII, using parentheses around
                accepting states, and with self-loops not drawn (labels
                simply written next to state).

                        a   b        b   a,b
                    -> q_e ---> q_b --->(q_bb)
                         |\_a__/

                Transition table (to be sure there is no confusion with my
                ASCII art above) -- initial is q_e, accepting are {q_bb}:

                    ___|_ q_e __ q_b __ q_bb _
                     a |  q_e    q_e    q_bb
                     b |  q_b    q_bb   q_bb

                Meaning of each state: for all w (- {a,b}*, \delta*(q_e,w)
                 = q_e iff w doesn't contain 'bb' and doesn't end with 'b';
                 = q_b iff w doesn't contain 'bb' and ends with 'b';
                 = q_bb iff w contains 'bb'.

         -  RE:  Easy: (a+b)*bb(a+b)*.

    (b) L_2 = { s in {a,b}* : s does not contain the substring bb }

         -  FSA:  Easy: same as above, except swap accepting/rejecting
                status of each state!

         -  RE:  RE's can only describe patterns that strings *have*, not
                patterns that strings do not have.  Must figure out how to
                turn negative into positive, i.e., figure out how to phrase
                "no substring bb" into what the string *can* contain.
                If 'bb' cannot appear, each 'b' in the string must be
                followed by 'a' (or be the last symbol in the string):
                    (a + ba)* (b + \epsilon)
                     == ((b+\epsilon)a)* (b+\epsilon)
                Equivalently, each 'b' in the string must be preceded by
                'a' (or be the first symbol in the string:
                    (b + \epsilon) (a + ab)*
                     == (b+\epsilon) (a(b+\epsilon))*