L is a regular language. Is $L′ = \{w \in L: |w| \bmod2=1\}$ a regular language?

Question

Let $L$ be a regular language.

$r$ is a regular expression that $L(r)=L$.

I'm trying to prove that $L′ = \{w \in L: |w| \bmod2=1\}$ is a regular language too.

To prove that language is a regular language I should prove 3 things:

1. There exists $r_1$ and $r_2$ such that $r = ((r_1) \cup (r_2))$

2. There exists $r_1$ and $r_2$ such that $r=((r_1)∘(r_2))$

3. There exists $r_1$ and $r_2$ such that $r = (r_1)^∗$

I'm having a problem to prove those 3 things.

Thank you for the help.

Answer 1

Note that the language $L_1 =\{w: |w| \equiv 1 \pmod 2\}$ is regular. Now let $D$ be a finite state machine that recognizes $L$, and let $D_1$ be a macine that recognizes $L_1$. You can then construct a "product machine" $D' = D\otimes D_1$ (see below), which recognizes $L' = L\cap L_1$. This proves that the intersection of two regular languages is a regular language.

Given two finite state machines $A, B$, their product $A\otimes B$ works the following way (what follows is basically a formalisation of "$A$ and $B$ runs in parallel"): Its states are ordered pairs $(a, b)$ of states $a$ from $A$ and $b$ from $B$. If $a_i, a_a$ are the initial and accepting states of $A$, and analoguously $b_i, b_a$ for $B$, then $(a_i, b_i)$ is the initial state and $(a_a, b_a)$ is the accepting state of $A\otimes B$.

If the mahine is in state $(a_1, b_1)$ and recieves input $x$, then it transitions into state $(a_2, b_2)$, where $a_2$ is the state that machine $A$ transitions into if it is in state $a_1$ and recieves input $x$, and similarily for $b_2$.

If $A$ and $B$ are both machines that accepts some regular language, say $L_A$ and $L_B$, then $A\otimes B$ accepts their intersection $L_A\cap L_B$. To see this, let's take a word $w$ and look at two cases:

1. $w\in L_A\cap L_B$. In this case, the characters in the word $w$, if given to machine $A$, will take it to the state $a_a$. It will also take machine $B$ to the state $b_a$. By definition of $A\otimes B$, it will take the product machine to state $(a_a, b_a)$, so it is accepted.
2. $w \notin L_A \cap L_B$. We may WLOG assume that $w \notin L_A$. This means that if we give the word $w$ to machine $A$, it will not end up in the accepting state $a_a$. This also means that if we give $w$ to the product machine, it cannot end up in the accepting state $(a_a, b_a)$. Thus the product machine does not accept $w$.