Class 1: Homework
You must print this sheet out and write/type answers on it!
This homework will define and, hopefully help you understand,
some of the basic notation involved with manipulating strings.
-
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!]
-
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.
- Let x = bba, y =
aab, and z = bcb. What is yxz?
- 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.]
-
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|?
-
Consider the mystery string λ. Suppose that for any string
w, we have |wλ| = |w|. What can you tell me about
λ?
-
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.
What is the "George" of abcccb?