5/14    I just flunked my theory of computation midterm. I'm a bit baffled
        at one of the questions that I got wrong. According to the answer
        key, L is finite state, but I'm pretty sure it's not.
        L={uvu^R | u,v  in {0,1}*, |v| is even}
        So I see that u and u^R are reverse, which already tells me that
        this is like Leq (need counting), hence not finite state. Is the
        answer key wrong, or I'm missing something obvious and stupid?
        \_ u^R means u backwards, right?  If so, any even-length string is in
           the language (let u be empty, and put the whole string in v).  No
           odd-length strings are in the language, because |v| would have to
           be odd.  So L is just the language of even-length strings.  --mconst
           \_ Thanks, yes L must be even. However, FS means that I'm able
              to build a machine with finite states, which means I should
              be able to represent it using regular expression. However,
              I can't possibly represent uvu^R because I need a push-down
              automaton to count for the reverse, so the answer should be
              be that L is NOT finite state, right?
              \_ /csua/tmp/regular-language  --mconst
              \_ How much space do you need to tell if a string has an
                 even number of characters?  -- ilyas
                 \_ Yes you're right, it is L={v | |v| is even}. I get
                    confused by that u^R thinking the string MUST conform
                    to that, but when in fact, it doesn't have to.
              \_ If your getting confused by uvu^R thinking you have to check
                 to make sure u is reversed with u^R, think of this:
                 Let v' = uvu^R.  Then consider u' = {} (and u^R = {}).  Now
                 u'v'u'^R is in the language because it was a string originally
                 in the language (its just uvu^R).  Maybe you can start to see
                 that the language is all the even strings, because just
                 consider both u and u^R to be the emptystring.  So you just
                 need to insure v is even (and hence can be recognized with a
                 DFA.)  -mrauser
        \_ Who takes midterms on May 14th?
           \_ Many people do.  I had two on May 14th.
              \_ What kind of whacked quarter/semester system in that?!