2. Show that there exists an algorithm for determining if L 1 ⊆ L 2 , for any
regular languages L 1 and L 2 .
3. Show that there exists an algorithm for determining if λ ∈ L, for any regular
language L.
4. Show that for any regular L 1 and L 2 there is an algorithm to determine
whether or not L 1 = L 1 /L 2 .
5. A language is said to be a palindrome language if L = L R . Find an algorithm
for determining if a given regular language is a palindrome language.
6. Exhibit an algorithm for determining whether or not a regular language L
contains any string w such that w R ∈ L.
7. Exhibit an algorithm that, given any three regular languages, L, L 1 , L 2 ,
determines whether or not L = L 1 L 2 .
8. Exhibit an algorithm that, given any regular language L, determines whether
or not L =
9. Let L be a regular language on Σ and be any string in . Find an algorithm
to determine if L contains any w such that is a substring of it, that is, such
that w = u υ with u,υ ∈ .
10. Show that there is an algorithm to determine if L = shuffle (L, L) for any
regular L.
11. The operation tail (L) is defined as
Show that there is an algorithm for determining whether or not L = tail (L)
for any regular L.
12. Let L be any regular language on Σ = {a, b}. Show that an algorithm exists
for determining if L contains any strings of even length.
13. Show that there exists an algorithm that can determine for every regular
language L, whether or not |L| ≥ 5.
14. Find an algorithm for determining whether a regular language L contains an
infinite number of even-length strings.
15. Describe an algorithm which, when given a regular grammar G, can tell us