$L$ is regular. Prove that $D(L)$ is also regular

90 Views Asked by At

I ask you for look at my solution: $L$ is regular. Prove that $D(L)=\{w|ww^R\in L, w\in\Sigma^*\}$ is also regular.

Idea
I go through states from two places (two fingers). When fingers meet in the same state I accept this word.

Formalisation
Automaton for $L:(Q,\Sigma, \delta, q_0, F)$
And for $D(L)(NFA):(Q',\Sigma, \delta', q_0',F')$
$Q'=Q\times Q$
$\delta'((q_1, q_2),a\in \Sigma) = \{(\delta(q_1,a), \delta^{-1}(q_1)\}$
$q_0'=\{(q_1, q_2):q_1 = q_0\wedge q_2\in F\}$
$F'=\{(q,q)|q\in Q\}$