Cpt S 317 Homework #2
Please print your name!
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
