Question

For any string $\mathbf{w}={\mathbf{w}}_1,{\mathbf{w}}_2,···,{\mathbf{w}}_n$, the reverse of w, written wR , is the string w in reverse order,${\mathbf{w}}_n···{\mathbf{w}}_2{\mathbf{w}}_1$. For any language $\mathbf{A},\mathbf{let}\mathbf{AR}=\left\{\mathbf{wR}|\mathbf{w}\mathbf{A}\right\}.$Show that if A is regular, so is AR.

Short answer

It means that$w\in A$ if$w^R\in A^R$

Step-by-step solution

To Convert the state for M

It recognizes A,

We have built a NFA for as follows:

Convert the start state for M as the only accept state $q_{accept}^{\text{'}}$for $M\text{'}$.

Add a new start state $q_o^{\text{'}}$for $M\text{'}$, and from $q_o^{\text{'}}$, add $\in -$transitions to $M\text{'}$each state of corresponding to accept states of M.

To Accept the State M

Here $q_o^{\text{'}}=q_{accept}^{\text{'}}$

For any $w\in \sum *$there is a path following w from the start state to an accept sate in M if there is a path following $w^R$from $q_o^{\text{'}}$to $q_{accept}^{\text{'}}$in $M\text{'}$

That means that $w\in A$if $w^R\in A^R$.