Determining if language is regular?

Question

Let $R$ be a regular language and $R_e := \{w\ |\ w \in R \text{ and the length of } w \text{ is even}\}$

Question: Is $R_e$ regular? Prove your answer.

I am having trouble with these type of questions. Can anyone help?

Answer 1

Yes: Intuitively, you can modify any automaton accepting $R$ to additionally keep track of the parity of the length of the string processed so far.

A little bit more formally, pick a finite automaton accepting $R$ and construct a new one accepting $R_e$ by doubling the set of states and having all transition maps go between the two copies of the states. The initial and terminal states of the original automaton are put in precisely one of the two copies.

Addendum with requested details: Suppose ${\mathcal R}$ is defined over the alphabet $\Sigma$ and that it is accepted by the finite automaton $({\mathcal S},s_0,{\mathcal T},\delta)$, where ${\mathcal S}$ are the states of the automaton, ${\mathcal T}$ are the terminal states, $\delta: {\mathcal S}\times\Sigma\to{\mathcal S}$ defines the state transitions and $s_0\in{\mathcal S}$ is the initial state. Then consider the automaton with state set ${\mathcal S}\times\{\text{even},\text{odd}\}$, initial state $(s_0,\text{even})$, terminal states ${\mathcal T}\times\{\text{even}\}$ and transition map $((s,\text{even}),x)\mapsto (\delta(s,x),\text{odd})$ and $(s,\text{odd}),x)\mapsto (\delta(s,x),\text{even})$. Then this automaton accepts precisely ${\mathcal R}_e$.

Note that this is a special case of the fact - proved very similarly way - that the intersection of two regular languages is again regular.