1. Consider the following languages over {0, 1}: L1 = {w : w begins and ends with the same symbols, |w|

2. Using the languages L1 and L2 from the previous problem, enumerate the first 6 strings in the L-ordering of the following. If there are fewer than 7 string, enumerate the entire language:

a) Suff(L2)

b) Pref(L1)

c) h(L1) where h(0) = ab and h(1) = c, = {a, b, c}

3. What are the unique substrings of w = ccabca over = {a, b, c}?

4. Give formal descriptions (5-tuples) for the DFAs shown in: a. Figure 1.10 (Sipser) b. Figure 1.22 (Sipser)

5. Give the state diagrams of DFAs recognizing the following languages over = {0, 1}:

a. L

b. L

c. {, 1, 101}

d. {w : w contains exactly three 1s}