1
$\begingroup$

Let $L$ is regular. Prove that $L'$ is regular. $ L'=\{uv: u\cdot rev(v)\in L\}$
$rev(v)=v^{-1}$
Idea:
$L^{-1}$ is regular and recognized by $R$, and $L$ by $M$. Let's assume that $M$ is NFA such that there is only one accepter. $q\in M$ is correponding to $q'\in R$. We add $\epsilon$-transition from $q$ to accept state in $R$. Formalisation:
$M=(Q_M, \Sigma, \delta_M, q_0, q_{acc})$
$R=(Q_M, \Sigma, \delta_R,q_{acc}, F_R) $
$M' = (Q, \Sigma, \delta, q_0, F )$
$Q=Q_M \cup (Q_M\times Q_M) $

$\delta (q, a\in \Sigma)=\delta_M(q, a) $
$\delta(q, \epsilon) = (a_{acc}, q)$
$\delta((q', r), a) = (\delta_R(q',a), r) $
$F=\{(q,q')\text{for each $q\in Q\}$} $

Is it ok ?

$\endgroup$
  • $\begingroup$ Could somebody glance at it ? $\endgroup$ – user220688 Mar 29 '15 at 8:42

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.