If L is a regular language then the language replace(L,σ,τ) is also regular

Question

I am stuck at the following problem:

---

Prove that if $L$ is a regular language over some alphabet $\Sigma$ and that $\sigma, \tau \in \Sigma$, Then the language $replace(L,\sigma,\tau)$ is regular.

Where $replace(L,\sigma,\tau)$ is defined as:

$replace(L,\sigma,\tau) = \{x\tau y\in \Sigma^*| x\sigma y\in L\}$.

---

My try:

Since $L$ is a regular language there exists a deterministic finite automaton $A=(\Sigma, Q, q_0, F, \delta_A)$ such that $L(A)=L$.

Now for each state $s\in Q$ we will define a non deterministic finite automaton $B_s=(\Sigma\cup\{\gamma\}, Q\times \{1,2\}, q_s, F\times \{2\}, \delta_{B_s})$ where $\gamma\notin \Sigma$ such that:

$\forall p\in Q,\mu\in\Sigma, \delta_{B_s}((p,1),\mu)=\{(\delta_A(p, \mu),1)\} $

$\forall p\in Q-\{s\}, \delta_{B_s}((p,1),\gamma)=\emptyset$

$\delta_{B_s}((s,1),\gamma)=\{(\delta_A(s,\sigma),2)\}$

$\forall p\in Q,\mu\in\Sigma, \delta_{B_s}((p,2),\mu)=\{(\delta_A(p, \mu),2)\} $

$\forall p\in Q, \delta_{B_s}((p,2),\gamma)=\emptyset$

Now we'all define a new non deterministic finite automaton with $\epsilon$ moves $B$ by linking he starting state of this automaton to all of the starting states of the automatons $B_{s}$ for every state $s$, And we will also link the final states of all of the $B_{s}$ automatons to the final state of the automaton $B$.

The automaton $B$ will satisfy the property $L(B)=\{x\gamma y|x\sigma y\in L\}$ ( This is probably incorrect!!!)

Now we will define an homomorphism $h:\Sigma\cup\{\gamma\}\longrightarrow\Sigma$ such that:

$\forall \mu\in\Sigma,h(\mu)=\mu$

$h(\gamma)=\tau$

Since regular languages are closed under homomorphisms we can conclude that $h(L(B))$ is regular, But $h(L(B))=h(\{x\gamma y|x\sigma y\in L\})=\{x\tau y|x\sigma y\in L\}$ and so $replace(L,\sigma,\tau)$ is regular over $\Sigma$.

---

Thanks for any hint or help.

Answer 1

Let $A$ be the alphabet and let $a$, $b$, $c$, ... be the letters (this is easier to type).

Hint. Consider the (non-deterministic) transducer $A^* \to A^*$ defined by $1 \xrightarrow{c \mid c}1\xrightarrow{a \mid b} 2 \xrightarrow{c \mid c} 2$ (more precisely, there are transitions $1 \xrightarrow{c \mid c} 1$ and $2 \xrightarrow{c \mid c} 2$ for any letter $c$ of $A$, including $a$ and $b$, but there is a single transition form $1$ to $2$). For each transition, the left hand part of the label is the input letter, the vertical bar is a separator and the right hand part is the output letter.

Answer 2

Use closure properties. Define homomorphisms $h_1$ and $h_2$ as follows:

$\begin{align*} h_1(x) &= \begin{cases} x & x \in \Sigma \\ \sigma & x = A \text{ (a new symbol)} \end{cases} \\ h_2(x) &= \begin{cases} x & x \in \Sigma \\ \tau & x = A \end{cases} \\ \end{align*}$

Then $h_2(h_1^{-1}(L) \cap (\Sigma^* A \Sigma^*))$ does the trick.