## Description

1. Let L be a regular language. Define End(L, a) = {x : x ∈ L and x is

ended with symbol a}. Show that End(L, a) is a regular language.

2. Assume that L is

((aa + bbb)

∗

c)

∗

.

What is a regular expression for language End(L, a)?

3. For a word x, we use x

r

to denote its reverse (e.g., the reverse of abaac is

caaba). For a language L, we use L

r

to denote {x

r

: x ∈ L}. Show that if L

is regular then so is L

r

.

4. Assume that L is

((aa + bbb)

∗

c)

∗

bc.

What is a regular expression for language L

r

?

5. Let L be a regular language defined by the following regular expression:

((aa + bbb)

∗ + ca)a

∗

(b + c).

List all the shortest words in L.

6. Describe an algorithm that finds all shortest words in a regular language

defined by a regular expression r.

1