# prove that language is regular (other language is regular)

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 ?

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