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.


2 Answers 2


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.

  • $\begingroup$ $\bar L$ is the complement of $L$. i.e: $\bar L = \Sigma^* \setminus L$ $\endgroup$
    – nir shahar
    May 31, 2020 at 18:13
  • $\begingroup$ Oh, I'm sorry, I realised that few seconds after submitting the comment. Ok, thank you! I'll work on it $\endgroup$
    – Mike
    May 31, 2020 at 18:15
  • $\begingroup$ Haha. Dont worry about it! $\endgroup$
    – nir shahar
    May 31, 2020 at 18:21

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.


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.