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?
   2. 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.]

   3. 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|?

   4. Consider the mystery string $x$. Suppose that for any string $w$, we have $|wx| = |w|$ What can you tell me about $x$?

3. We often represent the characters in a string like this: w = a₁a₂...a_k. Suppose I define the "George" of a string w = a₁a₂...a_k to be a₂a₁ a₄a₃ ... a_ka_k-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!