Prove that if $L$ is regular then $f(L)$ is regular

Question

Prove that if $L$ is regular then $f(L)$ is regular. $$f(L)=\{w: \text{every prefix of $w$ of odd length $\in$ L } \}$$

So my attemption is: Let $M= (Q, \Sigma, \delta, q_0,F) $ will be DFA recognizing $L$
Let construct $M'=(Q', \Sigma,\delta', q_0', F')$ recognizing $f(L)$.
$Q'=Q\times\{1,2\}$
$F'=\{(q,1)|q\in F\}\cup\{(q,2)|q\in F\}$
$q_0'= (q_0, 1)$
$\delta'((q,1),a\in\Sigma)=\begin{cases} (\delta(q,a),2);\delta(q,a)\in F\\ \emptyset; \delta(q,a)\notin F\end{cases} $
$\delta'((q,2), a\in\Sigma)=(\delta(q,a),1)$

What about this solution ?

$F'$ should be a subset of $Q'$. – J.-E. Pin Mar 26 '15 at 22:07 — J.-E. Pin, Mar 26 '15 at 22:07
I edited my post, look again please – user220688 Mar 29 '15 at 17:09 — user220688, Mar 29 '15 at 17:09

score 1 · Accepted Answer · answered Mar 26 '15 at 22:16

You can prove the result without using automata. Let $A$ be the alphabet, and let $$ K = \{ u \in A^* \mid \text{ every prefix of $u$ of odd length is in $L$} \} $$ Let $K^c$ be the complement of $K$ in $A^*$. Then \begin{align} K^c &= \{ u \in A^* \mid \text{ there exists a prefix of $u$ of odd length in $L^c$} \}\\ &= \{ u \in A^* \mid \text{ there exists a prefix of $u$ in $(A^2)^*A \cap L^c$} \}\\ &= \bigl((A^2)^*A \cap L^c\bigr)A^* \end{align} Therefore $K = \Bigl(\bigl((A^2)^*A \cap L^c\bigr)A^*\Bigr)^c$ and since regular languages are closed under intersection, complement, product and star, $K$ is regular.

Ok, Tomorrow I will look at your answer. But Im dying to know if my solution is properly ? — user220688, Mar 26 '15 at 22:23

Prove that if $L$ is regular then $f(L)$ is regular

1 Answers1

Linked