Given regular language $L$, is $L_1 = \{ w \mid \text{each prefix of } w \text{ of odd length} \in L \}$ regular?

Question

I was given a question and don't really know to solve it.

Given a regular language $L$, is the following language also regular? $$L_1 = \{ w \mid \text{each prefix of } w \text{ of odd length is in $L$} \}.$$

I think that $L_1$ should be regular, but I don't have a clue how to prove it.

Thank you for any input.

Answer 1

Try constructing an NFA for $\hat L:=\{w|$ there is an odd length prefix of $w$ that is $\notin L\}$, given a DFA for $\overline L$, and then show $L_1=\overline {\hat L} $.

If I'm not mistaken, this should work out.

Answer 2

There is a more economical solution for DFAs.

Suppose that $\langle Q,\Sigma,q_0,\delta,F \rangle$ is a DFA for $L$. We construct a DFA $\langle Q', \Sigma', q'_0, \delta',F' \rangle$ for $L_1$ as follows:

• $Q' = Q \times \{0,1\} \cup \{ q_{\mathit{sink}} \}$.
• $q'_0 = \langle q_0, 0 \rangle$.
• If $\delta(q,\sigma) \in F$ then $\delta'(\langle q,0 \rangle, \sigma) = \langle \delta(q,\sigma),1 \rangle$.
• If $\delta(q,\sigma) \notin F$ then $\delta'(\langle q,0 \rangle, \sigma) = q_{\mathit{sink}}$.
• $\delta'(\langle q,1 \rangle, \sigma) = \langle \delta(q,\sigma), 0 \rangle$.
• $\delta'(q_{\mathit{sink}}, \sigma) = q_{\mathit{sink}}$.
• $F' = Q \times \{0,1\}$.

What's going on here? The states $Q \times \{0,1\}$ keep track of both the state of the original automaton, and the parity of the current number of letters read. We are in one of these states as long as the condition "every odd-length prefix is in $L$" holds. If it stops holding, we move to a sink state.