1
$\begingroup$

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?

$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$ Commented Jan 27, 2020 at 18:34

3 Answers 3

2
$\begingroup$

Could you make a FA that accepts all and only even-length strings? What do you know about the intersection of two regular languages?

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.