# Show that if A is regular, then the subset containing only even language strings, is also regular

A language A, even(A) is the subset of A consisting of those strings in A of even length:

even(A) = { x∈A | |x| is even}


I need to use closure properties show that if A is regular, then even(A) is also regular.

Isn't that a definition called "A language is called a regular language if some finite automaton recognizes it", could prove even(A) is regular? How to use closure properties to prove this question?

• It's hard to provide a hint without giving it away completely, but you may want to use a correspondence between the regular languages and the even regular languages. – reinierpost Jan 27 at 18:34

You need to use one intersection operation. It is a known closure property that if two languages $$A, B$$ are regular, then the intersection $$A \cap B$$ will also be regular. In this case, $$A$$ is the given regular language. The other one, $$B = \textrm{Even}(\Sigma^*)$$, is the language of all even-length strings. The language you want to prove is the language containing all the strings in $$A$$ AND having even length [in $$B$$].
It is easy to show that $$B$$ is regular as well. Its regular expression is (..)*, where the period is the metacharacter that matches any character in the alphabet.
Your language is equivalent to determining that $$B$$ is regular, and then stating that $$A \cap B$$ is also regular. However, determining the regular expression of the intersection, will take doubly exponential time to do so.
Be careful, $$L_1 \subseteq L_2$$ with $$L_2$$ regular doesn't always mean that $$L_1$$ is regular. For one example, pick $$L_1 = \{a^n b^n \colon n \ge 1\}$$ (usually the first language proven non-regular), $$L_2 = \mathcal{L}(a^* b^*)$$ (defined by a regular expression, thus regular).