Name: ____________________________________________________ Alpha: _____________________

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. ```

```
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!