1
$\begingroup$

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\}$

$\endgroup$
  • 1
    $\begingroup$ Looks okay to me. $\endgroup$ – Brian M. Scott Apr 23 '15 at 22:06
  • $\begingroup$ You're welcome. $\endgroup$ – Brian M. Scott Apr 23 '15 at 22:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.