Name: ____________________________________________________ Alpha: _____________________

Describe help received: _________________________________________________________________

This homework will define and, hopefully help you understand, some of the basic notation involved with manipulating strings.

  1. Given the alphabet Σ = {a,b,c}, what is the language of all strings that start and end in c, with length at most three. [Remember: a language is by defintion a set!]
  2. Concatenation of strings, i.e. gluing strings together, is indicated by placing strings next to one another. so if w = abb and x = ba, then wx = abbba.
    1. Let x = bba, y = aab, and z = bcb. What is yxz?
    3. For strings u and v, is it always true that (uv)R = vu? Convince me of your answer! ["R" means reverse a string. So (abb)R = bba.]
    4. We denote the length of a string w as |w| ... like magnitude for a vector. For strings u and v, what can you say about |uv|?
    5. Consider the mystery string λ. Suppose that for any string w, we have |wλ| = |w|. What can you tell me about λ?
  3. We often represent the characters in a string like this: w = a1a2...ak. Suppose I define the "George" of a string w = a1a2...ak to be a2a1 a4a3 ... akak-1.
    1. What is the "George" of abcccb?
    2. What is the "George" of λ from the previous problem?
    3. Is there any string for which the "George" as I've described it is not unambigiously defined? Explain!
      Note: do not give "λ" as your answer!