Question

Explain your answer in each case.

(a) Every subset of a regular language is regular.
(a).True
(b).False
(b) Every regular language has a regular proper subset.
(a).True
(b).False
(c) If L is regular then so is {xy:x∈L and y∈L}. (d) {w:w=wᴿ } is regular.
(a).True
(b).False
(e) If L is a regular language, then so is {w:w∈L and wᴿ∈L}.
(a).True
(b).False
(f) {xyxᴿ :x,y∈Σ∗} is regular.
(a).True
(b).False

Answer 1

Not every subset of a regular language is regular, but every regular language has a regular proper subset. {w:w=wᴿ} is a regular language. If L is a regular language, then {w:w∈L and wᴿ∈L} is also a regular language.

Step-by-step explanation:

(a) Every subset of a regular language is regular. False. Not every subset of a regular language is regular. For example, consider the regular language L = n ≥ 0. The subset S = 0n1n is not regular.

(b) Every regular language has a regular proper subset. True. Every regular language has an empty language as a proper subset, which is regular.

(c) If L is regular then so is {xy:x∈L and y∈L}. False. {xy : x∈L and y∈L} may not be regular. For example, if L = 0n1n , then {xy : x∈L and y∈L} = 0n1n0n1n is not regular.

(d) {w:w=wᴿ } is regular. True. {w : w=wᴿ} represents the set of all palindromes, which is a regular language.

(e) If L is a regular language, then so is {w:w∈L and wᴿ∈L}. True. If L is regular, then {w : w∈L and wᴿ∈L} represents the set of all palindromes in L, which is regular.

(f) {xyxᴿ : x,y∈Σ∗} is regular. True. {xyxᴿ : x,y∈Σ∗} represents the set of all strings where the prefix and suffix are the same reversed strings, which is a regular language.